最長共通部分列 (LCS)

2 つの文字列に同じ順序で現れる文字の並びのうち、最も長いものの長さを求めます。

連続だと思い込む

"abcdef" と "acf" の答えは 3 です。a、c、f を順に拾えるからで、間に b や d が挟まっていても構いません。ここで隣り合った並びだけを探してしまうと、a か c か f の 1 文字しか取れず、答えを 1 と間違えます。

拾う文字は飛び飛びでよく、順序さえ入れ替わらなければ数えます。この 1 点を取り違えたまま進むと、遷移をどう直しても合いません。

候補を全部作ると、20 文字で 100 万通りを超える

文字を拾うか拾わないかを 1 文字ずつ決めるので、n 文字から作れる並びは 2 の n 乗通りあります。

6 文字で 64 通り、20 文字で 1,048,576 通り、40 文字なら 1 兆を超えます。片方の候補を全部作ってもう片方に含まれるか調べる方法は、ごく短い文字列でしか動きません。

末尾の 1 文字だけを見る

"abcde" と "ace" を並べて末尾を比べると、どちらも e です。一致しているなら、この e は答えの並びの最後に必ず使えます。使うと決めてしまえば、残るのは "abcd" と "ac" という一回り小さい同じ形の問題です。答えはその結果に 1 を足したものになります。

末尾が違うときは、どちらか一方の末尾が答えに使われていない、ということだけが分かります。どちらが余計なのかは決められないので、両方試して長いほうを採ります。

こうすると、見るべき問題は「a を先頭から何文字使うか」と「b を先頭から何文字使うか」の組み合わせだけになります。長さが n と m なら (n+1) * (m+1) 通りしかありません。100 万通りが数十通りに減ります。

解説

Git の差分表示や diff は、行を 1 文字と見なしてこれと同じ計算をしています。変わっていない行がどこまで共通して並ぶかを求め、そこから漏れたぶんを追加と削除として表示しています。

やってみよう

longestCommonSubseq(a, b) を書いてください。a を先頭から i 文字、b を先頭から j 文字使ったときの答えを入れる箱を、i と j の組み合わせのぶん用意します。どちらかが 0 文字なら答えは 0 です。あとは i と j を小さいほうから増やしながら、末尾が一致するかどうかで場合分けして埋めます。i 文字目の文字は添字 i - 1 にある、というずれに注意してください。最後に、両方を最後まで使ったところの箱を返します。

1. dp[i][j] を「a の先頭 i 文字と b の先頭 j 文字における LCS の長さ」と定義する
2. a[i-1] == b[j-1] のとき dp[i][j] = dp[i-1][j-1] + 1、それ以外は max(dp[i-1][j], dp[i][j-1])
3. 計算量 O(n * m)、メモリ O(n * m) で実装すること