3

Longest Common Substringのアルゴリズムを見つけました。これは通常、サイズのdynamic programming2 次元配列を使用して を使用して行われます。mxnmn

2 つの文字列に対して次の行列を作成します。

M[i][j] = 1 if s1[i]==s2[j] else 0.

たとえば、文字列が次の場合:abcxyおよびpqaabx

マトリックスは次のようになります。

    a b c x y
 p  0 0 0 0 0
 q  0 0 0 0 0
 a  1 0 0 0 0
 a  1 0 0 0 0
 b  0 1 0 0 0
 x  0 0 0 1 0

1ここで、左上から右下の方向にあるすべての対角線で s の最大連続シーケンスを検索します。

この中の最大値が答えになります。

配列を明示的に使用せずに上記の操作を実行できます。時間の複雑さはまだO(M*N)です。したがって、メモリは必要ありません。

誰かが私が間違っているところを指摘できますか?

4

2 に答える 2

1

アルゴリズムは正しいですが、標準の DP アプローチでは 2 番目のフェーズが省略され、ソリューションがよりシンプルになります。

ブール値をマークしてから対角線をスキャンして最長のシーケンスを探す代わりに、行列を構築するときに対角線の長さを計算できます。必要なパスは 1 つだけです。

時間と空間の複雑さに関しては、どちらのソリューションも O(NxM) です。ビット マトリックス表現を使用する場合、ソリューションはメモリをいくらか節約できますが、他のソリューションはおそらくわずかに高速です。

于 2014-02-27T15:05:17.803 に答える