最も長い一般的なサブストリングの長さの計算をスピードアップする方法は？

Question

私は2つを持っています 非常に大きな文字列 そして、私は彼らを見つけようとしています 最長の一般的なサブストリング.

1つの方法は使用です サフィックスツリー （複雑な実装ですが、非常に良好な複雑さを持っているはずです）、そして別のものは 動的プログラミング方法 （どちらも上記のWikipediaページに記載されています）。

動的プログラミングの使用

問題は、動的プログラミング方法には大きな実行時間があることです（複雑さは O(n*m), 、 どこ n と m 2つの文字列の長さです）。

私が知りたいこと（接尾辞ツリーを実装するためにジャンプする前）： 一般的なサブストリングの長さ（一般的なサブストリング自体ではない）の長さのみを知りたい場合、アルゴリズムをスピードアップすることは可能ですか？

Answer 1

実際には速いでしょうか？はい。 big-ohに関しては速いでしょうか？いいえ。動的プログラミングソリューションは常にO（n*m）です。

接尾辞ツリーで遭遇する可能性のある問題は、接尾辞ツリーの線形タイムスキャンを宇宙で大きなペナルティと交換することです。サフィックスツリーは、一般に、アルゴリズムの動的プログラミングバージョンに実装する必要があるテーブルよりもはるかに大きいです。文字列の長さに応じて、動的プログラミングがより速くなる可能性は完全にあります。

幸運を ：）

Answer 2

これらはそれをより速く実行させますが、それでも O(nm).

1つの最適化は、宇宙にあります（少し割り当て時間を節約するかもしれません）はそれに気づいています LCSuff 前の行にのみ依存します - したがって、長さのみを気にする場合は、最適化できます O(nm) にスペース O(min(n,m)).

アイデアは、2行のみを保持することです。処理している現在の行と、処理した前の行と残りを捨てることです。

Answer 3

これは、O（M+N）*log（M+N））で終了できる単純なアルゴリズムであり、O（M+N）ランタイムである接尾辞ツリーアルゴリズムと比較して実装がはるかに簡単です。

min common length（minl）= 0から始めましょう。

1. if (minL == maxL - 1), the algorithm finished with common len = minL.

2. let L = (minL + maxL)/2

3. hash every substring of length L in S, with key = hash, val = startIndex.

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1.

残りの問題は、時間O（n）の長さlですべてのサブストリングをハッシュする方法です。次のように、多項式式を使用できます。

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p.

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];

Answer 4

Myerのビットベクトルアルゴリズム あなたを助けられる。ビット操作を使用することで機能し、はるかに高速なアプローチです。