これは、「高価なアルゴリズムに対するClojureのパフォーマンス」という質問に対する@cgrandの回答のフォローアップです。私はそれを研究し、彼のテクニックのいくつかを私自身の実験的な Clojure パフォーマンス チューニングに適用しようとしています。

私が疑問に思っていることの1つは、「醜い」「配列スワップトリック」です。

これにより、元のアプローチよりもパフォーマンスが向上するのはなぜですか? Clojure 配列は真の Java プリミティブ配列ではない場合があるのではないでしょうか? 必要に応じて、回答で Clojure コア ソースを引用してください。

このコードを単純化または一般化する方法を誰かが知っているかどうか疑問に思っていました。正しい答えが得られますが、現在の状況にのみ適用されます。私のコードは次のとおりです。

私の質問は、2 番目の if ステートメントで、そのパターンが繰り返される一定量に設定されていることです (指定された文字列に適用されます)。しかし、\2 (パターンの繰り返し) を検索するために while ループを実行し続ける方法はありますか? 私が言いたいのは、これができるかということです: if ($someSequence =~ m/(([A][T])\2\2\2\2\2)/g) は while ループで単純化され、一般化されます

最長共通部分列アルゴリズムを実装し、最長の正しい答えを得ましたが、最長共通部分列を構成するものを出力する方法がわかりません。

つまり、最長の共通サブシーケンス配列の長さを取得することに成功しましたが、最長のサブシーケンスを出力したいと考えています。

このコードのプレイグラウンドはこちら

http://play.golang.org/p/0sKb_OARnf

タブが更新されたときにサブシーケンスを印刷しようとすると、結果が重複します。str1 と str2 に「GTABTABTABTAB」のようなものを出力したい

前もって感謝します。

私のコードは LCS の長さを計算するために機能しますが、次のリンクで LCS を読み取るために同じコードを適用します。

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

しかし、一部の文字列が欠落しています。私が欠けているものを教えていただけますか？

Google Playground リンク: http://play.golang.org/p/qnIWQqzAf5

前もって感謝します。

C++ の一連のファイル名から最長の共通部分文字列を計算する必要があります。

正確には、std::strings の std::list があります (または QT に相当するものも問題ありません)。

すべての文字列の n 個の異なる最長共通部分文字列を計算する必要があります。この場合、たとえば n=2 の場合です。

最長の共通部分列を計算できれば、それを切り取り、アルゴリズムを再度実行して 2 番目に長い部分列を取得できます。つまり、基本的には次のようになります。

std::strings の std::list の LCS を計算するための (リファレンス?) 実装はありますか?

これは良い答えではありませんが、私が持っている汚い解決策です-最後の「/」の後の部分のみが取得されるQUrlのQListに対するブルートフォース。これを「適切な」コードに置き換えたいと思います。

(私はhttp://www.icir.org/christian/libstree/を発見しました - これは非常に役立ちますが、私のマシンでコンパイルすることはできません。誰かがこれを使用したのでしょうか?)

たとえば、次のような文字列のペアがあります。abcabcabcandabcxxxabcと共通部分文字列ペア (LCSP) のリスト。この場合abc、最初の文字列の 3 つが 2 番目の文字列の 2 つにマップされるため、LCSP は 6 つのペアabcです。ここで、ペアの最長の有効な (インクリメントする) シーケンスを見つける必要があります。この場合、3 つの等しい長さの解があり 0:0,3:6; 0:0,6:6; 3:0,6:6ます。 」）。これを最長部分文字列ペア シーケンスまたは LSPQ と呼びます。（Qは文字列とシーケンスを混同しないでください）

この例の LCSP は次のとおりです。

今、私は総当たりで再帰的にすべての組み合わせを試して見つけました。そのため、約 25 ペアに制限されています。それ以外の場合は非現実的です。Size=[10,15,20,25,26,30], Time ms = [0,15,300,1000,2000,19000]

より長い入力 LCSP (共通部分文字列ペアのリスト) を使用できるように、線形時間または少なくとも 2 次複雑さでそれを行う方法はありますか。

この問題は「Longest Common Subsequence」に似ていますが、正確には違います。入力は 2 つの文字列ではなく、長さで並べ替えられた共通部分文字列のリストだからです。そのため、既存のソリューションをどこで探すべきか、または存在するかどうかさえわかりません。

ここに私の特定のコード（JavaScript）があります：

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です。誰かが私にどこで間違いを犯しているのか説明できますか

上級

文のリストで一般的な部分文字列を折りたたんで、それらが異なる領域のみを提示しようとしています。だからこれを取る：

そしてこれを返します：

詳細

• Longest Common Substring アルゴリズムを見てきましたが、それは 2 つの文字列しか比較していないようです。
• 文字列内の単語全体を比較することにのみ関心があります。
• 文字列を左から右に評価するだけです。
• 珍しい部分文字列の長さは、同じ単語数にはなりません (「猫」と「庭のヘビ」)

アルゴリズムのヘルプを探しています。これは LCS 問題の変種だと思います。ある種のサフィックス ツリーの処理だと思います。説明と実装の可能性がある疑似コードが理想的です。

もう一つの例

になる：

たぶん、このアプローチ

このアプローチはどうですか...