2

文字列のグループで最大の重複部分文字列を見つける方法を見つけようとしています。最長の重複部分文字列の問題は、通常、文字列のグループではなく、単一の文字列に適用されます。文字列のグループ内で最大の重複部分文字列を見つけるのに役立つアルゴリズムのタイプは何ですか？

（大きなソフトウェアライブラリの重複コードを削除するために）ファイルのグループで最大の重複文字列を見つけることが私が考えている主なユースケースですが、このアルゴリズムには他にも多くのユースケースがあります。

たとえば、この文字列のグループで最も長い重複部分文字列を見つけたいと思います。

"Hello world, this is the first string."
"Hello to the world, this is the second string."
"Hello world.  This is the third string."
"This is the third string."

この場合、"This is the third string."は最も長く繰り返される文字列（つまり、これらの文字列の複数に現れる最長の文字列）になります。

4

3 に答える 3

0

おそらくこれはあなたが探しているものですが、アルゴリズムを 3 つ以上の文字列に適用する必要があります。考えてみれば、それほど難しいことではありません。また、こちらのページもご覧ください。バックトラッキングを使用することは、あまり良い考えではありません。

于 2013-03-06T22:38:16.873 に答える
0

あなたの質問への答えはスライドから始まります 60 ここをクリック

基本的に、文字列入力 (線形時間) のすべての可能なサフィックスをリストします。それらを並べ替え（NLogN）、並べ替えられたリストを調べて最長のものを見つけます（線形時間）

于 2013-05-27T00:52:05.200 に答える
0
  1. 文字列ごと にTrie データ構造(プレフィックス ツリー) を作成する
    • T(i)文字列で呼び出しましょうi
  2. stringキーと値を使用して空のハッシュ マップを作成するint
    • 呼びましょうM
  3. 各 Trie T(i)、各ノードP(Pはプレフィックス文字列) に対してT(i)、
    • キーPがすでに にある場合はM、インクリメントしますM[P]
    • そうでなければ、挿入M[P] = 1
  4. 次のよう に(P*,C*)ペアを見つけます。M
    • C* >= 2(*)
    • length(P*)そのようなすべてのペアの中で最大です
  5. P*必要な文字列です

(*) 文字列に共通する最長の部分文字列を取得したい場合は、をK次のように置き換えます。2K

于 2013-05-27T02:11:40.567 に答える