最長共通部分列とは？
最長共通部分列(LCS, Longest Common Subsequence)は、2つの列で順序を保ちつつ必ずしも連続でなくてよい共通部分列のうち最長のものを見つける問題です。例えば ABCBDAB と BDCAB のLCSは BCAB(長さ4)です。
部分列(subsequence)は部分文字列(substring)と違い連続でなくて構いません — 間を飛ばしても順序さえ守ればよいのです。ファイル比較(diff)やバイオインフォマティクスのDNA比較に使われます。
状態の定義
dp[i][j] = Aの先頭i文字とBの先頭j文字が共有するLCSの長さ。
文字を1つずつ増やしながら「両端の文字が等しいか」だけ見ればよいように分かれます。
漸化式
Aのi番目の文字とBのj番目を比較します。
- •等しい(A[i] == B[j]):
dp[i][j] = dp[i-1][j-1] + 1(共通文字を1つ追加) - •異なる:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])(片方の文字を捨てた長い方)
等しければ対角線+1、異なれば上・左の大きい方 — この一行が核心です。
動作原理
ステップ1. 0行目と0列目を0にします(空文字列とのLCSは0)。
ステップ2. 表を左上から右下へ埋めます。各マスは上の漸化式で決まります。
ステップ3. dp[m][n] がLCSの長さです。
ステップ4(復元). 実際の列が必要なら dp[m][n] から逆に辿ります — 文字が一致すれば対角線へ移りその文字を記録し、異なれば大きい方へ移ります。
AlgoNoteの可視化は、表が埋まり文字が一致するとき対角線が強調される過程をステップごとに示します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(mn) |
| 空間 | O(mn) |
m, nは2つの列の長さです。長さだけ必要なら2行を回して空間をO(n)に減らせます。
例で追ってみる
A = ABCBDAB、B = BDCAB を比較すると
- •順序を保って取れる最長は
BCAB(またはBDAB)— 長さ4 - •表の右下マスの値が4になります
連続でなくてよい点に注意 — B, C, A, B が離れていても順序が合えば構いません。
よくあるミス
- •部分文字列との混同: LCSは連続を要求しません。連続が必要なら「最長共通部分文字列」という別問題です。
- •インデックス境界: 0行/0列(空文字列)を置かないと
dp[i-1]参照でずれます。 - •復元方向: 一致で対角線、不一致で大きい方 — 方向を間違えると違う列が復元されます。
AlgoNoteで直接確認しましょう
2つの列の文字を比較しながら表が埋まり、一致時に長さが伸びる過程をAlgoNoteでステップごとに確認できます。