最長共通部分文字列のこの方法は正しいでしょうか?

Question

のアルゴリズムを見つけました 最長の共通部分文字列. 。通常は次を使用して行われます dynamic programming, 、サイズの 2 次元配列を使用 mxn どこ m そして n は、考慮中の 2 つの文字列の長さです。

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左上から右下方向のすべての対角線にあります。

このうち最大値が答えとなります。

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

誰かが私が間違っているところを教えてくれませんか？

Answer 1

あなたの方法は正しいです。証明のために、S1 と S2 の最長の共通部分文字列が S1[i..j] と S2[p..q] からのものであると仮定します。これは、S1 [I+K] = S2 [P+K]を意味します

これらはすべて (i,p) から始まる対角線上にあります。

動的プログラミング ソリューションも同じことを行いますが、最初にテーブルを計算して対角のパスを通過する代わりに、対角の親に加えてそれらが一致するかどうかに応じてテーブルを計算します。

編集済み

追加メモリを使用するウィキペディアのソリューションに関するコメントについて。それは明確にするためにのみ存在します。原則として、wikipedia のソリューションでは行列の 2 行だけが必要で、現在の最大数を 1 つの変数に保持します。これは正しいです。行列内の (i,j) 番目のエントリに対して

M(i,j) = 1 + M(i-1, j-1) (s1[i] == s2[j]の場合)

ご覧のとおり、現在の行の要素はすぐ上の行の要素にのみ依存します。

Answer 2

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

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

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