最長共通部分列

$L [i] [j]$ の表を一致すれば $L [i - 1] [j - 1] + 1$ 、そうでなければ $max (L [i - 1] [j], L [i] [j - 1])$ で埋めて、2 つの文字列の最長共通部分列の長さを求められる

前提

動的計画法の基本（硬貨の最小枚数）（大学数学アルゴリズムと計算量）

説明

2 つの文字列に共通して含まれる「部分列」のうち、最も長いものの長さを、2 次元の表を埋める動的計画法で求めます。部分列とは、文字列からいくつかの文字を取り除き、残りを元の順番のまま並べたものです（とびとびでもよい）。たとえば $ABCBD$ から $BCD$ や $ABD$ が取り出せます。2 つの DNA 配列の似ている度合いや、2 つのファイルの差分（diff）を調べる場面の基礎になる計算です。

なぜそうしてよいのか

硬貨の問題では「 $n$ 円の答え」を「より小さい金額の答え」から作りました。ここでも同じ考え方を使います。文字列 $X = x_{1} x_{2} \dots x_{m}$ 、 $Y = y_{1} y_{2} \dots y_{n}$ について、先頭 $i$ 文字 $X_{i} = x_{1} \dots x_{i}$ と先頭 $j$ 文字 $Y_{j} = y_{1} \dots y_{j}$ の最長共通部分列の長さを $L [i] [j]$ とおきます。どちらかが空（ $i = 0$ または $j = 0$ ）なら共通部分列は空だけなので $L [i] [0] = L [0] [j] = 0$ です。求めたいのは $L [m] [n]$ です。今度は添字が 2 つあるので、表は 2 次元になります。

$x_{i} = y_{j}$ のとき： $X_{i - 1}$ と $Y_{j - 1}$ の最長共通部分列の後ろにこの文字を付ければよいので、 $L [i] [j] \geq L [i - 1] [j - 1] + 1$ です。逆に、 $X_{i}, Y_{j}$ の共通部分列 $Z$ を 1 つとります。 $Z$ の最後の文字が $x_{i}$ にも $y_{j}$ にも対応していないなら、 $Z$ は $X_{i - 1}, Y_{j - 1}$ の共通部分列なので、長さは $L [i - 1] [j - 1]$ 以下です。最後の文字が $x_{i}$ だけに対応しているなら、その文字は $x_{i} = y_{j}$ と等しいので、 $Y$ 側の対応先を $y_{j}$ に付け替えても共通部分列のままです（ $y_{j}$ だけに対応している場合も同様です）。こうして最後の文字が $x_{i}$ と $y_{j}$ の両方に対応している形にでき、それを取り除いた残りは $X_{i - 1}, Y_{j - 1}$ の共通部分列になります。どの場合も長さは $L [i - 1] [j - 1] + 1$ 以下なので、 $L [i] [j] = L [i - 1] [j - 1] + 1$ が成り立ちます。

$x_{i} \neq = y_{j}$ のとき：共通部分列の同じ 1 文字が $x_{i}$ と $y_{j}$ の両方に対応することはありえません（もし対応すれば $x_{i} = y_{j}$ になってしまいます）。したがって、 $x_{i}$ を使わない（ $X_{i - 1}, Y_{j}$ の共通部分列）か、 $y_{j}$ を使わない（ $X_{i}, Y_{j - 1}$ の共通部分列）かのどちらかです。よって $L [i] [j] = max (L [i - 1] [j], L [i] [j - 1])$ となります。どちらの式も「左上・上・左」のマスしか使わないので、表を上の行から順に、各行を左から右へ埋めれば、必要な値は常にそろっています。表は $(m + 1) (n + 1)$ マスあり、1 マスの計算は定数時間なので、全体の計算量は $O (mn)$ です。

手順

文字列を $X = x_{1} \dots x_{m}$ 、 $Y = y_{1} \dots y_{n}$ とし、 $(m + 1) \times (n + 1)$ の表 $L [i] [j]$ （ $0 \leq i \leq m, 0 \leq j \leq n$ ）を用意する。
0 行目と 0 列目をすべて 0 にする： $L [i] [0] = L [0] [j] = 0$ 。
$i = 1, \dots, m$ の順に行を選び、各行の中を $j = 1, \dots, n$ の順に進みながら、 $x_{i}$ と $y_{j}$ を比べる。
一致すれば $L [i] [j] = L [i - 1] [j - 1] + 1$ （左上 $+ 1$ ）、一致しなければ $L [i] [j] = max (L [i - 1] [j], L [i] [j - 1])$ （上と左の大きいほう）とする。
右下の値 $L [m] [n]$ が、最長共通部分列の長さである。

例題

文字列 $X = ABCBD$ と $Y = BDCB$ の最長共通部分列の長さを求めよ。

例題の解答

【手順1】 $m = 5, n = 4$ なので、 $6 \times 5$ の表を用意する。 $x_{1} \dots x_{5} = A, B, C, B, D$ 、 $y_{1} \dots y_{4} = B, D, C, B$ である。
【手順2】 $L [i] [0] = L [0] [j] = 0$ とする。
【手順3・4】1 行ずつ埋める（各行は $j = 1, 2, 3, 4$ の値を並べたもの）。
・ $i = 1$ （A）： $y_{j}$ はどれも A と一致しない。上も左も 0 なので、行は $0, 0, 0, 0$ 。
・ $i = 2$ （B）： $j = 1$ は B と B が一致するので $L [1] [0] + 1 = 1$ 。 $j = 2$ （D）は $max (0, 1) = 1$ 、 $j = 3$ （C）は $max (0, 1) = 1$ 。 $j = 4$ は B と B が一致するので $L [1] [3] + 1 = 1$ 。行は $1, 1, 1, 1$ 。
・ $i = 3$ （C）： $j = 1$ は $max (L [2] [1], L [3] [0]) = max (1, 0) = 1$ 。 $j = 2$ は $max (1, 1) = 1$ 。 $j = 3$ は C と C が一致するので $L [2] [2] + 1 = 2$ 。 $j = 4$ は $max (L [2] [4], L [3] [3]) = max (1, 2) = 2$ 。行は $1, 1, 2, 2$ 。
・ $i = 4$ （B）： $j = 1$ は一致するので $L [3] [0] + 1 = 1$ 。 $j = 2$ は $max (1, 1) = 1$ 。 $j = 3$ は $max (L [3] [3], L [4] [2]) = max (2, 1) = 2$ 。 $j = 4$ は一致するので $L [3] [3] + 1 = 3$ 。行は $1, 1, 2, 3$ 。
・ $i = 5$ （D）： $j = 1$ は $max (1, 0) = 1$ 。 $j = 2$ は D と D が一致するので $L [4] [1] + 1 = 2$ 。 $j = 3$ は $max (L [4] [3], L [5] [2]) = max (2, 2) = 2$ 。 $j = 4$ は $max (L [4] [4], L [5] [3]) = max (3, 2) = 3$ 。行は $1, 2, 2, 3$ 。
【手順5】 $L [5] [4] = 3$ である。実際、 $BCB$ は $X$ の 2・3・4 文字目、 $Y$ の 1・3・4 文字目として取り出せる共通部分列で、長さは 3 である。

答え: $3$

よくある誤り

部分列を「連続した部分（部分文字列）」と取り違える誤り。 $ABCBD$ と $BDCB$ では、連続して共通する部分は $BD$ や $CB$ の長さ 2 が最長です。正しくは、とびとびでもよいので $BCB$ の長さ 3 が答えです。
一致したときに、左上ではなく上や左のマスに $+ 1$ してしまう誤り。 $X = A$ 、 $Y = AA$ で $L [1] [2] = L [1] [1] + 1 = 2$ とすると、1 文字の $X$ と長さ 2 の共通部分列があることになり矛盾します。正しくは $L [1] [2] = L [0] [1] + 1 = 1$ で、左上から $+ 1$ します。
一致しないときに左上の値 $L [i - 1] [j - 1]$ をそのまま写してしまう誤り。 $X = AB$ 、 $Y = A$ で $L [2] [1] = L [1] [0] = 0$ とすると、共通の A を見落とします。正しくは $L [2] [1] = max (L [1] [1], L [2] [0]) = max (1, 0) = 1$ です。
0 行目・0 列目を作らずに、表を $m \times n$ にしてしまう誤り。この場合、 $i = 1$ や $j = 1$ で $L [i - 1] [\cdot]$ や $L [\cdot] [j - 1]$ を参照できなくなり、添字が 1 つずれてしまいます。正しくは、 $(m + 1) \times (n + 1)$ の表で $L [i] [0] = L [0] [j] = 0$ とし、 $L [i] [j]$ では $x_{i}$ と $y_{j}$ を比べます。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

最長共通部分列

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題