最長増加部分列・最長共通部分列
競技プログラミングでは、「最長増加部分列（LIS）」や「最長共通部分列（LCS）」を求めるものが出題されることがある。
これらは動的計画法により高速に求めることができる。
用語の意味
部分列
ある数列や文字列 $A=(a_1,a_2,...,a_N)$ がある時、部分列（Subsequence）とは、$A$ からいくつかの要素を抽出した列。
飛び飛びでもよいが、順番は元から変わってはいけない。
- $A=(3,1,4,1,5)$ とすると、
- $(3,1,1,5)$ や $(1,)$ などが部分列
- $(5,3)$ や $(1,1,4)$ は、元と並びが変わっているため部分列ではない
別の言い方をすると、以下の手順で構築できる列 $C$ が部分列である。
- $A$ の長さを $N$ として、$1 \le i_1 \lt i_2 \lt ... \lt i_k \le N$ を満たす添字列 $(i_1,...,i_k)$ を決める
- $C=(a_{i1},a_{i2},...,a_{ik})$ とする
空の列 $()$ を部分列に含むかどうかは定義による。
最長増加部分列
$A$ の部分列のうち単調増加なものを $A$ の「増加部分列」という。
同じ値を許すかは定義によるが、ここでは許さない（狭義単調増加）とする。
増加部分列のうち、長さが最も長いものを $A$ の「最長増加部分列」（Longest Increase Subsequence, LIS）という。
LISの具体的な要素は複数通り考えられる場合もあるが、長さは $A$ により一意に決まる。
| 元の数列 | $(5,3,7,4,1,4,6)$ |
| 増加部分列の例 | $(5,7),(3,6),(3,4,6)$ |
| 最長増加部分列の例 | $(3,4,6),(1,4,6)$ |
最長共通部分列
2つの列 $A$ と $B$ に共通する部分列を、$A$ と $B$ の「共通部分列」という。
そのうち長さが最長のものを「最長共通部分列」（Longest Common Subsequence, LCS）という。
LCSの具体的な要素は複数通り考えられる場合もあるが、長さは一意に決まる。
- $A=(1,2,3,4,5,6,7,8,9)$
- $B=(1,3,5,7,9,11,8,2,1)$
- 共通部分列の例
- $(1,2)$
- $(3,7,8)$
- 最長共通部分列の例
- $(1,3,5,7,9)$
アルゴリズム
最長増加部分列の長さ
動的計画法で求める。このアルゴリズムでは、最長増加部分列の内容自体は求まらない。
二分探索を用いる方法
- 空の配列 $L$ を用意する
- $A$ の要素を $i=1,2,...,N$ の順に1つずつ処理する。現在処理中の要素を $a_j$ とする。
- $L[i]$ は、「$a_1$～$a_j$ の要素から長さが $i+1$ の増加部分列を作ったとき、末尾要素が取り得る最小値」を意味する
- $L$ 上で二分探索して、$a_j$ 以上の値が初めて出てくるindex $k$ を求める。その後、$L$ を更新する
- $|L|=k$ なら、$L$ の末尾に $a_j$ を追加する
- $|L| \gt k$ なら、$L[k]$ を $a_j$ で置き換える
- 最後まで処理した後の $L$ の長さが、最長増加部分列長となる。
計算量 $O(N \log{N})$ で求めることができる。
狭義単調増加の場合はbisect_left（同じ値がある場合は最も左に挿入できるindexを取得）、広義単調増加の場合はbisect_right（同じ値がある場合は最も右に挿入できるindexを取得）を用いる。
from bisect import bisect_left
def lis(A: list):
L = [A[0]]
for a in A[1:]:
if a > L[-1]:
# Lの末尾よりaが大きければ増加部分列を延長できる
L.append(a)
else:
# そうでなければ、「aより小さい最大要素の次」をaにする
# 該当位置は、二分探索で特定できる
L[bisect_left(L, a)] = a
return len(L)
# -----------------------------------------
print(lis([3, 4, 5, 1, 6, 3, 2, 7])) # => 5
セグメント木（or BIT）を用いる方法
二分探索を用いる方法は、実装がシンプルではあるが、拡張性の面ではやや低い。
最長増加部分列を求めるのにはセグメント木を使う方法もあり、そちらは多少、ひねったバリエーション問題にも対応できる。
以下のDPを定義する。
- $DP[i]=a_i$ を末尾に必ず使用するような増加部分列の中で、最長のものの長さ
$DP[i]=0$（$i=1,...,N$）で初期化した上で、このDP配列をセグメント木に載せる。
$i$ ではなく、$a_i$ が小さい順に処理する。同率の場合は、indexが後の方から処理する。
$a_i$ について処理する際、$DP$ 配列の「$[1,i)$ の区間における最大値 + 1」が、$DP[i]$ となる。
区間最大値はセグメント木やBITで取得できるので、これで $DP[i]$ を計算し、更新する。
最終的に、$DP$ 全体の中での最大値が答えとなる。
こちらも計算量のオーダーは $O(N \log{N})$ となる。
二分探索と比べて定数倍や必要なメモリは重くなるが、一般的な競技プログラミングの制約の前ではまぁ、だいたい気にしなくていい。
最長増加部分列の復元
具体的な最長増加部分列の1つを求める場合。
二分探索を用いる方法で、$L$ の他に、以下の情報も持ってDPする。
- $prev[i]$: $a_i$ を更新したとき、$L[k]$ に格納したとして、その時点の $L[k-1]$ の値（先頭の場合は-1）
最後までDPしたら、復元する。
- $x=L[末尾]$ で初期化する。また、LIS復元用の配列 $S$ を空で初期化する。
- $A$ を逆順に走査する。$a_i=x$ となる $i$ が見つかったら、$S.append(x)$、$x ← prev[i]$ とする
- $x=-1$ になったら終了。$S$ を反転したものがLISとなる。
prevの記録・LISの復元は $O(N)$ でできるので、計算量は変わらず $O(N \log{N})$ となる。
最長増加部分列の個数
セグメント木を使う方法を拡張する。
- $DP[i]=a_i$ を末尾に必ず使用するような増加部分列の中で、(最長のものの長さ, その個数)
セグメント木なら、これは適切にマージできる。（長さが同じなら個数を合算し、どちらかが大きいならそちらを継承する）
$a_i$ について処理する際、$[0,i)$ の区間を求め、(最長の長さ+1, 個数) が $DP[i]$ となる。
計算量のオーダーは $O(N \log{N})$ となる。
最長共通部分列の長さ
2つの文字列A,Bがある時、「Aの部分列でもあり、Bの部分列でもある」文字列を共通文字列という。
そのうち最長のものを最長共通部分列（Longest Common Subsequence）という。
| A | abcbdabc |
| B | bdcaba |
| LCS | bcba,bdabなど |
この長さを求めましょう、という問題。（このアルゴリズムでは、最長共通部分列自体は求まらない）
- Bの要素を1つずつ順番に処理する。現在処理中の要素を$b_k$とする。
- $L[i]$を、「“$a_1$～$a_j$” と “$b_1$～$b_k$” から長さが $i+1$ の共通部分列が作れるとき、$j$ が取り得る最小値」とし、更新していく。
- Bを最後まで処理した後の $L$ の値が埋まっている所の長さが、最長共通部分列長となる。
def lcs(a: str, b: str):
L = []
for bk in b:
bgn_idx = 0 # 検索開始位置
for i, cur_idx in enumerate(L):
# ※1
chr_idx = a.find(bk, bgn_idx) + 1
if not chr_idx:
break
L[i] = min(cur_idx, chr_idx)
bgn_idx = cur_idx
else:
# ※2
chr_idx = a.find(bk, bgn_idx) + 1
if chr_idx:
L.append(chr_idx)
return len(L)
# ---------------------------------------
print(lcs('>abcbdabc', 'bdcaba')) # => 4
- 以下の解説にあたっての定義
- 文字列Bの先頭 $k$ 文字を抽出した文字列を、$B'_k$ とする
- $AT(S)$ を、「Aの部分文字列$S$ の末尾文字の、Aにおけるindex」とする
- A:abcabc、S:bb だった場合、$AT(S)=4$
- ※1:
- 処理中の文字を $b_k$ とする
- ※1の時点で
bgn_idxに入っているのは、$L[i-1]$、つまり「$AT(A$と$B'_{k-1}$ の長さ $i$ の共通部分列$)+1$」 - ここで「$A$と$B'_{k-1}$ の長さ $i$ の共通部分列」を $T$ とする（複数ある場合は、$AT(T)$ が最小のもの）
- ループ内でおこなっているのは、以下の確認
- $T$ の末尾に $b_k$ を付け足して長さ $i+1$ の共通部分列を作れるか？
- つまり、$AT(T)$ 以降に、文字 $b_k$ が存在するか？
- 作れたら、$AT(T+b_k)$ の値は？（これ+1が
chr_idx） - それは、既に発見済みの他の共通部分列$T'$ より短いか？（$AT(T+b_k)<AT(T')$ なら更新）
- 以上の繰り返しで、$L$ は更新される
- ※2:
- ループ途中でbreakされないで最後まで進むと、else節に入る
- ここで、$A$と$B'_{k-1}$ の最長共通部分列を $T_{max}$、その長さを $|T_{max}|$とする
- ※2の時点で
bgn_idxに入っているのは、「$AT(T_{max})+1$」 - Aにおいて、
bgn_idxより右に文字 $b_k$ が存在する ⇔ 最長共通部分列“$T_{max}+b_k$“が存在し、暫定最長共通部分列長を$|T_{max}|+1$に延長できる - 延長できる場合、$L$ に追加する
具体的な最長共通部分列
$(|S|+1) \times (|T|+1)$ の配列上でDPを行い、途中の計算結果を保存しておくことで、最長共通部分列と共に、その具体例を構築することが出来る。
DPテーブルの構築
$S_{1 ... i}$ と $T_{1 ... j}$ のLCSの長さを $L_{i,j}$ とする。
$L_{0,j}=0,L_{i,0}=0$ とする。
$S_{i+1}=T_{j+1}$ の時
LCS長は1文字拡張できる。$L_{i+1,j+1}=L_{i,j}+1$
それ以外の時
LCS長は、片方の末尾を1文字削った2通りの長い方となる。 $L_{i+1,j+1}=max(L_{i+1,j},L_{i,j+1})$
これで、$i=1 .. |S|$、$j=1 .. |T|$ の2重ループでDPテーブルを小さい方から埋めていくことで、$L_{|S|,|T|}$ が最終的なLCS長となる。
具体例の構築
具体的な文字列は、DPテーブルから逆向きに復元する。$(i,j)=(|S|,|T|)$ とする。
$L_{i,j}=L_{i,j-1}$ または $L_{i,j}=L_{i-1,j}$ の時
同じである数字の方に$(i,j)$を移動する。両方同じ場合は、具体例が1つ構築できればいい場合は適当に1つ選んで移動する。
それ以外の時
$S_i=T_j$ であるはずなので、それをLCSに加え、$(i-1,j-1)$ に移動する。
0 1 2 3 4 5 6 7
M Z J A W X U
0 | 0 0 0 0 0 0 0 0
1 X |⓪ 0 0 0 0 0 1 1
2 M | 0❶① 1 1 1 1 1
3 J | 0 1 1❷ 2 2 2 2
4 Y | 0 1 1② 2 2 2 2
5 A | 0 1 1 2❸③③ 3
6 U | 0 1 1 2 3 3 3❹ 丸付きの数字を辿っていき、
7 Z | 0 1 2 2 3 3 3④ 黒丸の数字を拾っていくと、LCS（の1つ）は MJAU と復元できる
