最長共通部分列

最長共通部分列（LCS）は、二列に同じ相対順序で現れる最長の列です。選んだ位置の間に隙間を許します。コード diff の整列の基礎となり、共通部分を骨格として残し、それ以外を追加・削除などで扱えます。

同じ旅行の二つの記憶が、異なる詳細を持ちながら同じ順の出来事を含む形です。LCS は詳細を飛ばせますが、残す出来事の順は変えません。

LCS の仕組み

長さ m には空を含め 2^m 通りの位置選択があります。同じ文字があれば、別の選択が同じ内容になることもあります。全部生成して b に含まれるか調べると指数費用です。DP は接頭部の比較結果を再利用します。

dp[i][j] は a[:i] と b[:j] の LCS 長。行 0 と列 0 は空の接頭部なので 0 です。

a[i - 1] == b[j - 1] なら、末尾の一致で次を使います。

dp[i][j] = dp[i - 1][j - 1] + 1

現在の二位置を除いた解へ一文字を加えるので左上です。上や左に一を加えると、現在位置を重複使用する恐れがあります。

異なれば一方の末尾を捨て、長い方を取ります。

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

同点は両方の縮め方が最適長を保つという意味です。ここでは上を優先して再生と結果を固定しますが、LCS が一意になるわけではありません。

右下は長さだけです。文字は逆追跡し、一致で対角へ進んで出力、不一致で同じ長さを保つ隣へ移ります。

最も早い一致の貪欲法が短くなる理由

a = ABCBDAB、b = BDCABA で a を左から読み、b の最初の利用可能な一致を選ぶとします。最初の a[0] = A を b[3] と組むため、b[0..2] = B, D, C を越え、もう使えません。

続いて b[4] の B、b[5] の A を取り、ABA、長さ 3 です。有効な共通部分列ですが最長ではありません。

DP は上と左の選択肢を保ち、b の添字 0、2、4、5 を使う BCBA、長さ 4 を復元します。一回の局所的に早い一致が、よりよい全体の対応を閉ざす場合があります。

計算をステップで追う

既定は ABCBDAB と BDCABA。

1. 貪欲法が a[0] の A を b[3] へ対応付ける。消した B、D、C は以後使えない位置。
2. a[1] の B を b[4]、a[5] の A を b[5] に合わせ、ABA、長さ 3 を比較用に残す。
3. DP の行 0、列 0 を 0 にし、空との比較を解く。
4. 行ごとに左から埋める。A と B、D、C の最初の三セルは候補が 0 なので 0。dp[1][4] は A 同士で左上 0 に一を加え、dp[2][1] も B 同士で 1。
5. 不一致では上か左の大きい方。dp[3][5] は両方 2 で、同点規則により上。
6. dp[7][6] = 4 が完成し、空の四結果位置を表示。長さは既知、文字は未復元。
7. (7, 6) から、B と A が異なり、上が 4 を保つので (6, 6) へ。A が一致し、右端へ A を入れて (5, 5) へ対角移動。
8. (5, 5) から上の (4, 5) で B が一致。対角後、(3, 4) から左の (3, 3) へ進み C が一致。
9. 対角の (2, 2) から左の (2, 1) で B が一致し、最初の位置を埋める。順に読むと BCBA、長さ 4。

別の合法な同点規則なら BDAB、同じ長さ 4 も得られます。表は最適長を証明し、逆追跡はそれを実現する一例を示します。

時間・空間計算量

m、n は二列の長さです。列挙の界は各候補を b で O(n) 検査する仮定で、候補生成自体にも費用があります。長さだけなら二行、または慎重に更新する一行に圧縮し、O(min(m, n)) 空間です。文字の復元には追加情報が必要なため、ここでは全表を保存します。

境界ケース

• 一方が空なら空列、長さ 0。
• 共通文字がなければ全セル 0、出力なし。
• 重複文字は複数の最適経路を作り得る。同点規則は再現性を与える。
• 同一列なら全体が LCS。
• 部分列は隙間を許し、連続を要求する部分文字列とは異なる。

よくある間違い

• 一致で max(top, left) + 1。 左上を延長します。
• 不一致でも一を加える。 新しい共通文字はありません。
• 初期の零同点を複雑な分岐と考える。 両候補 0 なら 0 を書いて進みます。
• 空の行列を省く。 境界の依存先を失います。
• 依存前にセルを埋める。 上、左、左上を先に完成させます。
• 最も早い一致は常に安全と思う。 最初の A を b[3] に合わせると BCBA を支える前方を失います。
• 復元列を唯一と呼ぶ。 最適長は固定でも、実現する列は複数あり得ます。