algorithm
最長共通サブシーケンス
サーチ…
最長共通部分シーケンス説明
ダイナミックプログラミングの最も重要な実装の1つは、 最長共通サブシーケンスを見つけることです。最初にいくつかの基本的な用語を定義しましょう。
サブシーケンス：
サブシーケンスは、残りの要素の順序を変更せずにいくつかの要素を削除することによって、別のシーケンスから派生できるシーケンスです。文字列ABCがあるとします。この文字列からゼロまたは1つ以上の文字を消去すると、この文字列の部分列が得られます。したがって、文字列ABCの部分列は{ "A" 、 "B" 、 "C" 、 "AB" 、 "AC" 、 "BC" 、 "ABC" 、 " }}になります。すべての文字を削除しても、空文字列は部分列になります。サブシーケンスを見つけるには、文字列の各文字について、我々は文字を取るか、そうでないかの2つの選択肢があります。したがって、文字列の長さがnの場合 、その文字列の2 n個の部分列があります。
最長共通サブシーケンス：
名前が示すように、2つの文字列の間のすべての共通部分配列のうち、最も長い共通部分配列（LCS）は、最大長を持つものです。例えば：「HELLOM」および「HMLD」との間の共通部分列は「HL」、「HM」などここで、「HLL」、「H」であり、長さ3を有し、最長共通サブシーケンスです。
ブルートフォース方式：
バックトラッキングを使用して2つの文字列のすべての部分列を生成することができます。次に、それらを比較して共通の部分列を見つけることができます。最大の長さのものを見つける必要があるでしょう。私たちはすでに、長さnの文字列の2 n個の部分列があることを見てきました。私たちのnが20-25を超える場合、問題を解決するには数年かかるでしょう。
動的プログラミング方法：
私たちの方法に例をあげてみましょう。 2つの文字列abcdafとacbcfがあるとします。これらをs1とs2としましょう。したがって、これらの2つの文字列の中で最も長い共通部分列は、長さが4の"abcf"になります。もう一度言いますが、部分列は文字列内で連続である必要はありません。 "abcf"を構築するには、 s1の "da"とs2の "c"を無視しました。ダイナミックプログラミングを使用してこれをどのように見つけ出しますか？
まず、行のs1のすべての文字とs2のすべての文字を列に持つテーブル（2D配列）から始めます。ここでは、テーブルは0でインデックス付けされており、1から順番に文字を配置します。各行の左から右へテーブルを移動します。私たちのテーブルは次のようになります：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
ここで、各行と列は、2つの文字列間の最長の共通部分列の長さを表し、その行と列の文字を取り、前の接頭辞に追加するとします。例： Table [2] [3]は、 "ac"と"abc"の間の最も長い共通部分列の長さを表します。
0番目の列は、 s1の空の部分列を表す。同様に、0行目はs2の空の部分列を表す。文字列の空の部分列を取り、別の文字列と一致させようとすると、2番目の部分文字列の長さに関係なく、共通部分列の長さは0になります。したがって、0番目の行と0番目の列を0で埋めることができます。我々が得る：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
さぁ、始めよう。 テーブル[1] [1]を塗りつぶすときに、文字列aと文字列aがあり、それ以外の文字列があれば、ここで最も長い共通部分列は何でしょうか？ここでLCSの長さは1になります。次に表[1] [2]を見てみましょう。文字列abと文字列aがあります。 LCSの長さは1になります。ご覧のとおり 、 abcd 、 abcda 、 abcdafの文字列aのみを考慮しているため、残りの値も1行目に1となります。だから私たちのテーブルは次のようになります：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
行2の場合、これにはcが含まれます 。 表[2] [1]については、片側にはacがあり、反対側にはaがあります。 LCSの長さは1です。これはどこから取得しましたか？上から、2つの部分文字列の間のLCS aを示します。したがって、 s1 [2]とs2 [1]が同じでない場合、LCSの長さは、 上端または左端のLCSの長さの最大値になります。最上部のLCSの長さを取ることは、現在の文字をs2からとらないことを意味します。同様に、左のLCSの長さを取ることは、LCSを作成するためにs1から現在の文字を取得しないことを示します。我々が得る：
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
最初の数式は次のようになります。
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
テーブル[2] [2]については、文字列abとacがあります。 cとbは同じではないので、ここでは上または左の最大値を設定します。この場合、再び1です。その後、 表[2] [3]に対して、文字列abcとacがあります。今回は、行と列の両方の電流値が同じです。今度はLCSの長さはLCSの最大長と今までの+ 1の長さに等しくなります。これまでのLCSの最大長はどうでしたか？対角の値をチェックします。これは、 abとaの最適な一致を表します。この状態から、現在の値について、同じように起こったs1とs2にもう1つの文字を追加しました。 LCSの長さはもちろん増加します。 表[2] [3]に1 + 1 = 2を入れます。我々が得る、
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
だから私たちの2番目の式は次のようになります
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
両方のケースを定義しました。これらの2つの公式を使用して、テーブル全体を読み込むことができます。テーブルを埋めると、次のようになります。
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
s1とs2との間のLCSの長さは、 Table [5] [6] = 4となる 。ここで、5と6はそれぞれs2とs1の長さです。私たちの疑似コードは次のようになります：
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
このアルゴリズムの時間複雑度は次のとおりです。O（mn）ここで、 mとnは各文字列の長さです。
最長の共通部分列をどのように見つけ出すか？右下隅から始めます。私たちは価値がどこから来ているかをチェックします。 表[i-1] [j-1]がTable [i] [j] -1と等しい場合、 s2 [i]またはs1 [j] （両方同じです）、斜めに移動します。値が上から来る場合、つまりTable [i-1] [j]がTable [i] [j]と等しい場合は、先頭に移動します。値が左から来る場合、つまりTable [i] [j-1]がTable [i] [j]と等しい場合は、左に移動します。一番左または一番上の列に達すると、検索が終了します。スタックから値をポップして印刷します。擬似コード：
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
点に留意すべき：[I] [J-1] 表に等しい表[I-1]〜[J]とテーブルの両方場合は[I] [J]と表[I-1] [J-1]ではありませんTable [i] [j] -1と等しい場合、その瞬間に2つのLCSが存在する可能性がある。この擬似コードはこの状況を考慮しません。複数のLCSを見つけるには、これを再帰的に解かなければなりません。
このアルゴリズムの時間複雑度は、 O（max（m、n））である 。