1

2 つの文字列の最長共通部分列を返す Python 関数を実装しました。ここで、任意の数の文字列の最長共通部分列を返す関数を実装したいと思います。

3つの文字列についてこのヘルプを見つけました：

dp[i, j, k] = / 1 + dp[i - 1, j - 1, k - 1] if A[i] = B[j] = C[k]
              \ max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise

しかし、私はこのヒントをよく理解していません。だから、誰かが私を助けることができれば、私は感謝します. よろしく、マーク

4

4 に答える 4

1

LCS 問題は、文字列 n の無制限数に対する NPComplete です。つまり、これを解決できる既知の多項式アルゴリズムはありません。また、DPソリューションをドロップできることも意味します:p

複数の文字列の LCS を概算するヒューリスティックな方法へのリンクを次に示します。

http://www.aai.org/ocs/index.php/AAAI/AAAI10/paper/download/1559/2197

于 2012-05-23T21:41:38.787 に答える
1

ローリング ハッシュを使用したバイナリ検索に似た処理を行うことで、時間内にこれを行うことができますO(N log(N))(ここで、N はシーケンスの組み合わせの長さです)。

可能な限り長い共通シーケンスの長さは、最小のシーケンスの長さであることに注意してくださいsmallestLength。次のように進めます。

初期化:

  • 最長の共通サブシーケンス ( と呼びますa) の長さはa=であると仮定しますsmallestLength/2

アルゴリズム：

  • iteration_number += 1
  • すべてのリストをスキャンし (必要に応じて並行して!)、ローリング ハッシュを実行します。これにより、各リストの len(list)-(a-1) ハッシュが生成されます
  • すべてのハッシュをセット データ構造 (リストごとに 1 セット) に挿入して、O(1) ルックアップ時間を実現します
  • ハッシュのいずれかが衝突するかどうかを確認します (すべてのセットの共通部分を取ります): 1 つ以上の衝突がある場合はa、ハッシュが間違っている可能性があるため、それらの位置に -length サブシーケンス共通サブシーケンスがあることを手動で確認します (ただし、十分に細かいハッシュを選択した場合、これは実際には発生しません)
  • 共有シーケンスを見つけましたか？
    • そのようなシーケンスが見つかった場合は、上記の手順を繰り返しますが、バイナリ検索の場合と同様に想定される長さを増やします (追加smallestlength/2**iteration_number)
    • そのようなシーケンスが見つからない場合は、上記の手順を繰り返しますが、バイナリ検索の場合と同じように想定される長さを減らします (減算smallestlength/2**iteration_number)
于 2012-05-23T21:44:01.647 に答える