内容別リスト/データ探索系/最長共通部分列 - 競技プログラミング用 知識集積所【7/12更新】

---

雑な説明

2つの数列または文字列の一部（連続でなくてもよい）を拾って全く同じ数列または文字列を作るとき、最長でどのくらいの長さのものを作れるか？という問題。
動的計画法の応用で解ける。

レベル

ABCのE問題以降。

アルゴリズム内容

例えば

A = {1, 2, 3, 4, 5}
B = {1, 4, 3, 5, 2}

という2つの数列があったとする。
この場合、

C = {1, 4, 5}

という数列はAからもBからも「数列の一部だけを拾う」という方法で作ることができる。
こういう場合、CはAとBの共通部分列という。
共通部分列の中で最も長いものを最長共通部分列といい、これを求めたり利用する問題を競プロでときどき見かける。
これは、二次元の動的計画法を用いて以下のような方法で解ける。

まず、以下のように表を作る。

B＼A	-	1	2	3	4	5
-	0	0	0	0	0	0
1	0	1	1	1	1	1
4	0	1	1	1	2	2
3	0	1	1	2	2	2
5	0	1	1	2	2	3
2	0	1	2	2	2	3

青色：AとBで値が一致しているので、左上+1
黄色：AとBで値が一致していないので、左と上の大きい方
赤色：片方の長さが0なので明らかに0

この時点で、右下のマスを見て最長共通部分列の長さは3だとわかる。
ここから、実際の最長共通部分列を作るには以下のようにする。

表の右下からスタートして、

• AとBの値が同じなら、その値を記録してから左上へ進む（黄色）
• AとBの値が異なるなら、左マスと上マスで値が大きい方（同じならどちらでも）へ進む（赤色）

を0と書き込まれたマスにたどり着くまで繰り返すと、最長共通部分列が後ろから順に出来上がる。

B＼A	-	1	2	3	4	5
-	0	0	0	0	0	0
1	0	1	1	1	1	1
4	0	1	1	1	2	2
3	0	1	1	2	2	2
5	0	1	1	2	2	3
2	0	1	2	2	2	3

なお、3歩目で上ではなく左へ行くと、{1,4,5}ではなく{1,3,5}というものができる。
最長共通部分列は1つとは限らないが、普通の問題であれば別解として認められる。

別手法

実は、最長増加部分列を使っても解ける。
例えば

A = {1, 2, 3, 1, 2}
B = {1, 3, 3, 2, 1}

の最長共通部分列を探す場合。

まず、Aの0番目と一致するものをBの後ろから探し、その位置を記録する。

vec

4

0

Aの1番目と一致するものをBの後ろから探し、その位置を続きに記録する。

vec

4

0

3

Aの2番目と一致するものをBの後ろから探し、その位置を続きに記録する。

vec

4

0

3

2

1

Aの3番目と一致するものをBの後ろから探し、その位置を続きに記録する。

vec

4

0

3

2

1

4

0

Aの4番目と一致するものをBの後ろから探し、その位置を続きに記録する。

vec

4

0

3

2

1

4

0

3

このvecの最長増加部分列を求めると{0,1,3}となる。
Bから対応する位置の値を拾って、{1,3,2}がAとBの最長増加部分列となる。

注意点

関連アルゴリズム

動的計画法

再帰的問題、つまり「少し小さい問題の答えがわかっていれば簡単に答えが出る」というタイプの問題を高速に解くアルゴリズム。
最長共通部分列を求めるのに使われている。

バックトラック

終了状態から逆再生しながら何かを調べるアルゴリズム。
最長共通部分列そのものを復元するためにお世話になる。

最長増加部分列

数列の一部（連続でなくてもよい）を拾って単調増加列を作るとき、最長でどのくらいの長さのものを作れるか？という問題。
最長共通部分列を最長増加部分列のアルゴリズムで解く方法がある。