最長共通部分列 (LCS)

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

連続だと思い込む

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

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

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

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

s = "abcdef"
count = 1
for char in s:
    count = count * 2   # この文字を拾うか、拾わないかの二通り
print(count)   # 64

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 文字と見なしてこれと同じ計算をしています。変わっていない行がどこまで共通して並ぶかを求め、そこから漏れたぶんを追加と削除として表示しています。

やってみよう

ひな形の TODO を完成させてください。文字一致なら斜めから増加、不一致なら上と左を比較を自分で書きます。入力を受け取る枠と説明つきの準備部分はそのまま使えます。

演習で使う書き方

例は "sun" と "son" です。末尾の n が一致するので、"su" と "so" の答えに一つ足します。末尾が違う箱では上と左の大きいほうを選びます。表の確保と、上・左の箱を読む変数を用意しました。比較と遷移を書く際は通常の if を使い、条件式を使う必要はありません。

1. 文字一致なら斜めから増加、不一致なら上と左を比較を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える