Longest Common Subsequence

lcs(i, j)を、接尾辞text1[i:]とtext2[j:]に対する答えとします。それぞれの先頭の文字を見てみましょう。等しければ、その2文字を組にします。この組を使わない最長共通部分列でも、最初の組をこの組に置き換えて、長さを短くせずに済みます。したがって、答えは1 + lcs(i+1, j+1)です。

文字が異なる場合、両方を使うことはできません。それぞれをもう一方の文字列の後ろにある文字としか対応づけられず、組が交差してしまうためです。そこで、どちらか一方を削除できます。答えはmax(lcs(i+1, j), lcs(i, j+1))です。どちらかの接尾辞が空なら、共通するものはないので、答えは0です。

不一致のたびに2つの呼び出しが始まるため、処理が遅くなります。2つの文字列に共通する文字がない場合、どちらかの文字列が尽きるまで、すべての呼び出しで不一致になります。そして、呼び出しの数は2つの文字列を交互に並べる方法の数のように増加します。20文字の文字列2つでは、呼び出し回数は約2.8 × 10^11回です。大きなテストでは、それぞれの文字列に1000文字あります。それでも、異なる組(i, j)は(n+1) × (m+1)個しかないため、ほとんどの呼び出しは以前の呼び出しを繰り返しています。

状態。 dp[i][j]を、text1の最初のi文字とtext2の最初のj文字の最長共通部分列とします。接頭辞を使うことで、インデックス0を空文字列として扱えます。

漸化式。 2つの接頭辞の最後の文字、text1[i-1]とtext2[j-1]を比較します。等しければ、それらを組み合わせます。dp[i][j] = dp[i-1][j-1] + 1。異なる場合は、どちらか一方を除きます。dp[i][j] = max(dp[i-1][j], dp[i][j-1])。これは、末尾から考えた再帰と同じ考え方です。基本ケース: 空の接頭辞はどの文字列とも共通部分を持たないため、0行目と0列目は0です。順序: 各セルは上のセル、左のセル、左上斜めのセルを参照するため、行ごとに左から右へ埋めていけば、参照先は常に計算済みです。答えはdp[n][m]です。

pearとreapの場合、peaに対応する行は[0, 0, 1, 2, 2]です。reaに対応するセルが2なのは、aとaが一致するためです。したがって、peとreに対応するセルの値1に1を加えます。最後のセルでは、pearとreapを比較し、rとpは異なるため、隣接する2つのセルのうち大きい方の値である2を取ります。

表のセル数は(n+1) × (m+1)で、それぞれの計算にかかる時間は一定です。1000文字の文字列2つの場合、約10^6ステップです。再帰をメモ化したバージョンも同じセルを埋めますが、再帰呼び出しの深さは最大でn + mになり、Pythonなどの言語ではデフォルトのコールスタックをオーバーフローさせます。

表の行 i は、行 i-1 とその行のそれ以前のセルだけを読み取ります。行の処理が終わると、それより上の行が再び読み取られることはありません。そのため、完成した行用の prev と、埋めている行用の cur の2つの配列を使い、各行の後にそれらを入れ替えます。漸化式と順序はまったく同じままです。

2つの文字列の最長共通部分列は、どちらの文字列が先かを問わないため、それらを入れ替えて、行が短い方の文字列に沿って進むようにできます。すると各行が保持する数値は min(n, m) + 1 個になります。最大の入力でも、100万個のセルの代わりに1001個で済み、処理量は同じ 10^6 ステップです。

各行の最初の要素は、短い方の文字列の空の接頭辞を表すため、0のままにする必要があります。答えは、最後に完成した行の最後の要素です。