問題タブ [lcs]

のような文字列が与えられた場合、文字"geekthegeertheregeers"列自体で最も長い共通部分文字列を見つける必要があります。

この場合の"geer"ように、最長の共通部分文字列になります。私の質問は、ここでどのアルゴリズムが適用されるかということです。この問題のこの解決策を見つけるために LCS を変更できますか?

2 つのシーケンスがあり、最長の共通サブシーケンスを見つける必要があります。関数の復元が機能しない理由がわかりません。

私が行った場合

関数リターン

その問題はインデックスにあると思いますが、どこにあるのかわかりません。

私は先週 LCS 問題を勉強していて、質問があります。

最長のサブシーケンス自体 (長さだけでなく) を見つけることにも関心があるときはいつでも、補助 (string1.length X string2.length) 行列を作成し、上矢印、左矢印、または斜め矢印を追加してサブシーケンスを決定します。 、元の場所に対応するため、後で手順をたどってサブシーケンス自体を見つけることができます。

(ここで例を参照してください: http://www.columbia.edu/~cs2035/courses/csor4231.F13/lcs.pdfの最後のページ)

私の質問は次のとおりです。次の 2 つの文字列を実行するための次の出力マトリックスを検討してください。

空間の複雑さを増やさなくても、マトリックスの最後の列だけに基づいて、共通のサブシーケンスを見つけることができるというのは本当ですか?

考えられるすべての LCS と 2 つの文字列の位置をそれぞれ報告できるようにするプログラムを完成させました。ただし、テスト ケースの出力は完全に正しいわけではありません。

たとえば、2 つの文字列が「AACADBCDADCB」と「DCACDCBBDBAD」の場合、正しい結果は 8 ケースを報告するはずです。私の出力は、以下のように 6 つのケースを報告するだけです。

--- 出力 --- 最大。長さ = 7
LCS: ACDBDAD 、X の場合: 2 3 5 6 8 9 10 、Y の場合: 3 4 5 7 9 11 12
LCS: ACDBDAD 、X の場合: 2 3 5 6 8 9 10 、Y の場合: 3 4 5 8 9 11 12
LCS: ACDCDAD 、X の場合: 2 3 5 7 8 9 10 、Y の場合: 3 4 5 6 9 11 12
LCS: CADBDAD 、X の場合: 3 4 5 6 8 9 10 、Y の場合: 2 3 5 7 9 11 12
LCS: CADBDAD 、X 軸: 3 4 5 6 8 9 10 、Y 軸: 2 3 5 8 9 11 12
LCS: CADCDAD 、X 軸: 3 4 5 7 8 9 10 、Y 軸: 2 3 5 6 9 11 12

いくつかの提案をお願いします。ありがとうございます！

複数のシーケンスで最長共通部分文字列 (LCS) を見つけようとしています。

CPAN には、次のような 2 つのシーケンスの LCS アルゴリズムを実装するモジュールが多数あります。Algorithm::差分と String::LCSS_XSですが、複数のシーケンスにわたる LCS は必ずしもそれらの 2 つの間の LCS であるとは限らないため、2 つ以上のシーケンスで動作するようにそれらを拡張するのに苦労しています。

その名前に反して、Algorith::MLCSは実際には LCS を返すのではなく、多数の配列のすべての共通要素 (これも非連続) を返すことに注意してください。設計上壊れているという印象ですが、間違っているかもしれません。

Algorithm::DiffとAlgorith::MLCSは、最長共通部分文字列の問題ではなく、最長共通部分列の問題を解決します。

n=2 アルゴリズムを拡張する明白な方法はありますか、それとも自分のバージョンを実装する必要がありますか? はいの場合、どのように？

ありがとう。

Common Childのプログラミング チャレンジでは、一般的な Longest Common Substring 問題とは異なるアプローチを取りました。コードは

小さい TestCases を使用すると、解決策を得ることができますが、より長いテストケースの解決策を得ることができません。

私がしたことは

入力: ABCDEF - FBDAMN とします - コードに挿入されるので b とします。出力: 2. BD は部分文字列です。

したがって、ここで行っているのは、a の各部分文字列の一致可能な部分文字列をチェックし、最大のものを出力することです。すなわち。ここで最も外側のループを表す ABCDEF、BCDEF、CDEF、DEF、EF、F の部分文字列 (ループ i)

2 番目のループは、文字列内の各文字に一致します。(1...n)、(2...n)、(3...n)、...、(n) を反復します。つまり、i が指定する文字から開始します。

次に、3 番目のループが文字列 B 全体を繰り返し処理して、a[j] が B の文字と一致するかどうかを確認し、一致する場合はカウントを増やします。

部分文字列から文字を削除することしかできないため、ごちゃ混ぜにすることはできません。つまり、各文字は両方の文字列で同じ相対的な順序である必要があるため、前の文字が見つかった後、x を使用して B を検索しています。

ドライランは例のようになります（0からn-1までの配列）

a= abcdef b= fbdamn

i=0 の場合 - 文字列全体が一致する abcdef

x=-1 なので、k は 0 から n-1 まで繰り返すので、a=f? a=b? a=d? a=a? カウント = カウント + 1; したがって、x は 3(a の位置) として設定されます。A の a の後の要素は、B の a の後にしか出現しないため、x=3 です。したがって、k は 4 から 5 まで繰り返されます。 b=m? b=n? c=m?c=n? ... ... ... ...

以前のカウントよりも大きい場合は、以前のカウントの値を保存します。したがって、maxcount=count で、count を 0 にリセットし、位置を x=-1 にリセットします。

i=1 ie string = BCDEF k from 0 to n だから、B=F? b=b? count=count+1 // 1 になる x を 1(B の位置) とする k 2 から nc=d? c=a?c=m?c=n? k は 2 から nd=d まで? count = count+1 // 2 になる x は 2 k として 3 から ne=a?e=m?e=n? まで 3 から nf=a?f=m?f=n? までの k 次に、最大カウント (コード内の prev) が現在のカウントより大きい場合、最大カウント = カウント、リセット カウント = 0、x=-1; CDEF、DEF、EF、Fの場合、ここの最大部分文字列は2になります。

長いテストケースではなく、短いテストケースで機能します。

それが機能するテストケースは次のとおりです。

OUDFRMYMAW AWHYFCCMQX

出力2付

機能しません

WEWOUCUIDGCGTRMEZEPXZFEJWISRSBBSYXAYDFEJJDLEBVHHKS FDAGCXGKCTKWNECHMRXZWMLRYUCOCZHJRRJBOAJOQJZZVUYXIC

正しい出力は15で、私の出力は10です。誰かが私にどこで間違いを犯しているのか説明できますか