問題
英大文字からなる2つの文字列 $A$（長さ $N$）と $B$（長さ $M$）が与えられる。
最長共通部分列（LCS）の長さと、実際のLCSの文字列を1つ求めよ。ただし通常の $O(NM)$ 空間のDP表を保持する方法ではなく、Hirschberg のアルゴリズム（分割統治により $O(NM)$ 時間・$O(\min(N,M))$ 空間で復元する手法）に基づいて、以下の手順で一意に定まるLCSを求めること。
手順の定義
lcs_len_row(S, T): 通常のLCS長DPの最終行（長さ $|T|+1$）だけを $O(|T|)$ 空間で計算する関数hirschberg(A, B): $|A|=0$なら空文字列、$|A|=1$なら $A[0]\in B$ か判定して返す。それ以外は $\mathrm{mid}=\lfloor|A|/2\rfloor$ とし、$L_1=\mathrm{lcs\_len\_row}(A[0:\mathrm{mid}],B)$、$L_2=\mathrm{lcs\_len\_row}(\mathrm{reverse}(A[\mathrm{mid}:]),\mathrm{reverse}(B))$ を計算、$L_2$を反転した $L_2^r$ と合わせ $\mathrm{total}[j]=L_1[j]+L_2^r[j]$ が最大となる最小の $j=k$ で分割し、$\mathrm{hirschberg}(A[0:\mathrm{mid}],B[0:k]) + \mathrm{hirschberg}(A[\mathrm{mid}:],B[k:])$ を返す
入力形式
A
B制約
入出力例
入力例1
AGCAT
GAC出力例1
2
GA入力例2
ABCBDAB
BDCABA出力例2
4
BDAB概念図
ヒント（段階的開示）
ヒント1（方向性）
通常のLCS復元はDP表全体を保持するため $O(NM)$ 空間が必要。しかし長さだけなら1行前の情報だけで計算でき $O(M)$ 空間で済む。Hirschbergのアイデアは「$A$を真ん中で割ったとき、最適LCSは$B$のどこかの位置$k$で必ず分割できる」事実を使い、その$k$を長さだけの計算（前から1回・後ろから1回）で特定し、文字列復元は再帰の中でのみ行う点にある。
ヒント2（アプローチ）
$A$を前半 $A[0:\mathrm{mid}]$ と後半 $A[\mathrm{mid}:]$ に分けたとき、$\mathrm{LCS}(A,B)=\mathrm{LCS}(A[0:\mathrm{mid}],B[0:k])+\mathrm{LCS}(A[\mathrm{mid}:],B[k:])$ が成り立つ $k$ が存在する。この$k$を、前半から見た$B$各接頭辞へのLCS長($L_1$)と、後半を逆順にして見た$B$各接尾辞逆順へのLCS長($L_2$を反転した$L_2^r$)の和 $L_1[j]+L_2^r[j]$ を最大化する $j$ として求める。
ヒント3（誘導）
def lcs_len_row(S, T):
prev = [0]*(len(T)+1)
for i in range(len(S)):
cur = [0]*(len(T)+1)
for j in range(len(T)):
if S[i] == T[j]:
cur[j+1] = prev[j] + 1
else:
cur[j+1] = max(prev[j+1], cur[j])
prev = cur
return prev
def hirschberg(A, B):
if len(A) == 0:
return ""
if len(A) == 1:
return A if A[0] in B else ""
mid = len(A) // 2
L1 = lcs_len_row(A[:mid], B)
L2 = lcs_len_row(A[mid:][::-1], B[::-1])
L2r = L2[::-1]
# total[j] = L1[j] + L2r[j] が最大となる最小の j を選ぶ
...
return hirschberg(A[:mid], B[:k]) + hirschberg(A[mid:], B[k:])max(range(len(B)+1), key=lambda j: total[j]) は最初に最大値を達成したインデックスを返す点がタイブレークと自然に一致する。
模範解答 (Python)
import sys
def lcs_len_row(S, T):
m = len(T)
prev = [0] * (m + 1)
for i in range(len(S)):
cur = [0] * (m + 1)
si = S[i]
for j in range(m):
if si == T[j]:
cur[j + 1] = prev[j] + 1
else:
pv = prev[j + 1]
cv = cur[j]
cur[j + 1] = pv if pv > cv else cv
prev = cur
return prev
def hirschberg(A, B):
if len(A) == 0:
return ""
if len(A) == 1:
return A if A[0] in B else ""
mid = len(A) // 2
L1 = lcs_len_row(A[:mid], B)
L2 = lcs_len_row(A[mid:][::-1], B[::-1])
L2r = L2[::-1]
best_k = 0
best_v = -1
for j in range(len(B) + 1):
v = L1[j] + L2r[j]
if v > best_v:
best_v = v
best_k = j
left = hirschberg(A[:mid], B[:best_k])
right = hirschberg(A[mid:], B[best_k:])
return left + right
def main():
data = sys.stdin.read().split()
A, B = data[0], data[1]
ans = hirschberg(A, B)
print(len(ans))
print(ans)
main()Step-by-Step 解説
$dp[i][\cdot]$の計算には$dp[i-1][\cdot]$しか使わないので、1行分の配列を使い回せば$O(M)$空間でLCSの長さだけは求まる。
$\mathrm{LCS}(A,B)$のDP表で、$A$の中央行における最適経路は必ずどこかの列$k$を通過する。$L_1[j]+L_2^r[j]$を最大化する$j$がまさにこの分割点$k$になる。
「$A[\mathrm{mid}:]$と$B$全体を逆順にしてから前から計算する」ことで、逆順の$j$番目が元の$B[j:]$に対応するLCS長を全ての$j$について一括で得られる。
各再帰段で使うのは$O(M)$の一時配列のみで呼び出し終了後に破棄されるため、同時生存空間は$O(\min(N,M))$に抑えられる。
各段の$A$分割幅の総和が各段で$N$に等しいため、全体の時間計算量は通常のDPと同じ$O(NM)$に収まる。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
total[j]のタイブレークを「最後に見つかった$j$」にしてしまう | >=で更新してしまう | >のときのみ更新し最小の$j$を採用 |
| $|A|=1$の基底ケースで先頭一致だけを見てしまう | $B$のどこかにあれば長さ1のLCSになることを見落とす | in演算子で$B$全体を判定 |
| $L_2$を反転せず$L_1[j]+L_2[j]$としてしまう | 逆順計算した配列がそのまま対応すると誤解 | $L_2$は反転してから$L_1$と対応させる |
| 再帰のたびに文字列全体をコピーし続け実質$O(N^2)$の余分なコストがかかる | スライスが新しい文字列を作ることを意識しない | 本問の制約では許容範囲だが、空間効率を追求する場合はインデックス範囲だけを渡す設計にする |
| $N=0$または$M=0$を特別扱いせず再帰が無限ループする | 基底ケースの実装漏れ | $|A|=0$の基底ケースを必ず用意する |
次のステップ
- 発展: 本問の分割統治を使い、LCSだけでなく編集距離（レーベンシュタイン距離）の最適な操作列を $O(NM)$ 時間・$O(\min(N,M))$ 空間で復元するように拡張せよ。
- 発展2: $N,M \le 5000$ 程度まで制約を上げ、$O(NM)$ 表全体を保持する素朴な復元法との実行時間・メモリ使用量を実測比較せよ。