php - 共通部分文字列を見つける

Question

N 個の文字列があります。少なくとも 2 文字の長さで、少なくとも 2 つの文字列に含まれるすべての部分文字列を探しています。

次の文字列の場合:

1. 私の名前はダニエルです
2. 名前は何？
3. 彼らは私をダニエルと呼んでいます

返されるはずです（1文字のみの文字列を除く）：

• 「名前」 – 1. & 2.
• 「は」 – 1. & 2.
• 「ダニエル」 – 1. & 3.
• 「私」 – 1. & 3.
• "y" – 1. & 3.

文字列の長さは非常に長くなる可能性があります (1KB ～ 10KB)。メモリの問題はほとんどありません (~2GB) - これらの一般的な文字列をできるだけ早く計算する必要があるだけです。

前もって感謝します！ダニエル。

Answer 1

データベースに 3 つのテーブルを作成することをお勧めします。

1. テキストからの単一の単語を保持するインデックス テーブル
2. テキストを保持するテーブル
3. 単語からテキストへの参照を保持するテーブル

アプローチは次のようになります。

1. 文字列をテキスト テーブルに追加する(2)
2. 文字列を単語で分割する
3. すべての単語: 単語がインデックス (1) テーブルにない場合は追加します。
4. すべての単語に対して: 参照テーブル(3)にエントリを追加し、単語とテキスト テーブルにリンクします。

この構造があれば、特定の単語、それらがどのくらいの頻度で発生するか、どこで発生するかを非常に簡単に数えることができます。

単語の索引表に索引を付けると、非常に高速に検索できます。

Answer 2

私の最善の選択肢は、文字列間のすべての可能な組み合わせ (およそ n^2 の組み合わせ) を作成し、各組み合わせに対して LCS アルゴリズムを実行することであることがわかりました。これで、すべての結果を比較してそれらを処理できます。

それは O(n^2*m^2) - LCS アルゴリズムの実行ごとに O(m^2) の n^2 の組み合わせです。

私はそれが素朴な実装であることを知っていますが、私が見つけることができる最高のものです.

とにかくありがとう ：-）