問題タブ [lcs]

指定された 2 つの文字列の最長共通回文サブシーケンスの長さをカウントする効率的なアルゴリズムはありますか?

例えば：

文字列 1。 afbcdfca

文字列 2。 bcadfcgyfka

LCPS は 5 で、LCPS 文字列はafcfaです。

次の I/O を行う LCS のバージョンを実装するとします。

入力: superLCS('猫','車')

出力: ['ca#','ca#']

現在、私のプログラムはそのために機能しますが、文字がずれていると機能しません。

たとえば、入力が superLCS('art','cad') の場合、出力は ['###','###'] になります。['a##','##a#'] が出力されているはずです

コード：

プログラムの完成に近づいていますが、小さな問題があります。I/O は次のようになります。

しかし、私の場合は次のことを行います：

適切な回答が得られるように、誰かが私のコードを編集してください。私はそれを理解することはできません。ありがとう：

プログラムが返す必要がある I/O は次のとおりです。

fanlc2("x", "y")

[0, '#', '#']

fanlc2("スパム", "")

[0, '####', '']

fanlc2("スパ", "m")

[0, "###", "#"]

fanlc2("猫", "車")

[2, "ca#, "ca#"]

fanlc2("猫", "lca")

[2、「ca#」、「#ca」]

fanlc2("人間", "チンパンジー")

[4, 'h#man', '#h#m#an###']

こんにちは仲間のプログラマー、

文字列のニアマッチに関して、助けを求めたいと思います。

現在、説明の文字列を保存するプログラムがあります。ユーザーは、説明の全部または一部を入力して説明を検索できます。

ほぼ一致する検索を実装したいと思います。たとえば、実際の説明は「hello world」ですが、ユーザーが誤って「helloeorld」という検索を入力しました。プログラムは、ユーザーに「helloworld」を返すことができる必要があります。

パターンと一致を調べて実装しようとしましたが、文字列と一致するために正規表現が必要であるため、説明に規則的なパターンがありません。string.containsも試しましたが、どちらも機能しないようです。以下は私が実装しようとしたコードの一部です。

仲間のプログラマーがこれを手伝ってくれませんか？

LCS の並列計算は、波面パターンに従います。これは、シリアル実装より遅い並列関数です。（対角線の数（並列）と行数（直列）が関係していると思います）

ここにシリアル関数があります

...テスト機能を追加すると思いました

最長共通部分列問題に関して、すべてのオンラインリソースで提示されている基本的なアルゴリズムは私には明らかです。このアルゴリズムの説明は次のとおりです。

私がはっきりしていないのは、次のようにどこにでもあるアルゴリズムの動的計画法バージョンのために提示されたアルゴリズムです。

しかし、DPバージョンがどのように同等であるかはわかりません。私が困っているのは、DPバージョンでX[i] == Y[j]は、内側のループでそれを見つけたときに、同じでDPを計算し続けるという事実iです。つまり、内側のループの残りの部分は同じと比較し続けX[i]ます。再帰的アルゴリズムはC[i-1、j-1]を評価する必要があると言っているので、次の手順に進むべきではありませんiか？

最長の共通部分列を見つけるアルゴリズムを設計しました。これらは手順です：

• 最初の文字列の最初の文字を選択します。

• 2 番目の文字列でそれを探し、見つかった場合は、その文字を に追加し、 common_subsequenceその位置を に保存します。そうでない場合は、 の長さと の長indexさを比較し、 大きい場合は、その値を に代入します。common_subsequencelcslcs

• 最初の文字列に戻り、次の文字を選択して、前の手順をもう一度繰り返しますが、今度はindex番目の文字から検索を開始します

• 選択する最初の文字列に文字がなくなるまで、このプロセスを繰り返します。最後に、の値はlcs最長共通サブシーケンスです。

これは例です:
</p>

最初の文字列を選択Aします。で
を探します。 2 番目の文字列にがあるので、それを に追加します。 最初の文字列に戻り、次の文字を選択します。今度は の位置から 2 番目の文字列を探します。 の後にあるので、 に B を追加します。 次に、最初の文字列の次の文字を選択します。2 番目の文字列には次の toはありません。したがって、その長さが の長さより大きいため、common_subsequence の値を に割り当てます。最初の文字列の終わりに到達するまで、前の手順を繰り返します。結局の値はAY
Acommon_subsequence
BBA
BAcommon_subsequence
CCBlcslcslcs最長共通部分列です。

このアルゴリズムの複雑さは theta(n*m) です。ここに私の実装があります：

最初のアルゴリズム:

ハッシュ テーブルを使用した同じアルゴリズム:

配列を使用せずに最も長い共通部分列を見つけるにはどうすればよいですか? ocaml の折り畳みリストのみ

最長共通サブシーケンス アルゴリズムについての簡単な質問です。次のように、サブシーケンスを生成する必要がある部分を実行しました。

printDiff 関数は次のようになります。

そして、これをパラメーターとして使用すると:

lcsLength() で opt マトリックスを生成した後、printdiff が私に与えてくれることを望みます:

しかし、代わりに私は得る:

私が何を間違えたのかについてのアイデアは、私を大いに助けてくれるでしょう

ありがとうローラン

2 つの文字変数 (オブジェクトの名前) があり、最大の共通部分文字列を抽出したいと考えています。

結果として次のことが必要です。

これらのベクトルを入力として使用すると、同じ結果が得られるはずです。

これらの例は代表的なものです。文字列には識別要素が含まれており、各ベクトル要素のテキストの残りの部分は共通ですが不明です。

次のいずれかの場所に解決策はありますか (優先順):

1. ベースR

2. おすすめパッケージ

3. CRAN で利用可能なパッケージ

想定される重複への回答は、これらの要件を満たしていません。