Day 090-Q3 — Hirschberg's Algorithm（線形空間LCS復元）

問題

英大文字からなる2つの文字列 $A$（長さ $N$）、$B$（長さ $M$）が与えられる。$A$ と $B$ の最長共通部分列（LCS）を1つ出力せよ（複数ある場合はどれでもよい）。ただし通常の $O(NM)$ サイズのDPテーブルは保持せず、$O(N+M)$ 程度のメモリで実際のLCS文字列を復元する分割統治アルゴリズム（Hirschberg's Algorithm）を実装すること。

入出力例

ABCBDAB
BDCABA

BDAB

AGCAT
GAC

GA

例1: LCS長は4。`BDAB`以外にも`BCBA`, `BCAB`等が正解として扱われる（特別ジャッジ）。

概念図: $A$ を中央分割し、$B$ 上の最適な分割点 $k$ を探す

ヒント

def hirschberg(a, b):
    if len(a) == 0: return ""
    if len(a) == 1: return a if a in b else ""
    mid = len(a) // 2
    left = lcs_len_row(a[:mid], b)
    right = lcs_len_row(a[mid:][::-1], b[::-1])
    total = [left[j] + right[len(b)-j] for j in range(len(b)+1)]
    k = max(range(len(b)+1), key=lambda j: total[j])
    return hirschberg(a[:mid], b[:k]) + hirschberg(a[mid:], b[k:])

模範解答

import sys

def lcs_len_row(a, b):
    m = len(b)
    prev = [0] * (m + 1)
    for i in range(1, len(a) + 1):
        cur = [0] * (m + 1)
        ai = a[i - 1]
        for j in range(1, m + 1):
            if ai == b[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                pv, cv = prev[j], cur[j - 1]
                cur[j] = 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 in b else ""
    if len(b) == 0:
        return ""
    mid = len(a) // 2
    left_row = lcs_len_row(a[:mid], b)
    right_row = lcs_len_row(a[mid:][::-1], b[::-1])
    m = len(b)
    best_j, best_val = 0, -1
    for j in range(m + 1):
        v = left_row[j] + right_row[m - j]
        if v > best_val:
            best_val = v
            best_j = j
    return hirschberg(a[:mid], b[:best_j]) + hirschberg(a[mid:], b[best_j:])

def main():
    data = sys.stdin.read().split()
    a, b = data[0], data[1]
    sys.setrecursionlimit(10000)
    print(hirschberg(a, b))

main()

計算量: 時間 $O(NM)$（標準DPと同じオーダー）。メモリは $O(N+M)$ に削減（再帰の深さ $O(\log N)$ × 各レベル $O(M)$ の一時配列）。

Step-by-Step 解説

Step 1: 長さだけならロールング配列で十分な理由

$dp[i][j]$ の計算には $i-1$ 行目しか使わないため、2行分の配列を使い回せば長さだけなら $O(\min(N,M))$ メモリで済む。

Step 2: 分割点を見つける仕組み

left_row[j] は $A_L$ と $B[:j]$ のLCS長、right_row[m-j] は $A_R$ と $B[j:]$ のLCS長。この和を最大化する $j$ が全体のLCS長と一致する（区分最適性）。

Step 3: 逆順DPで末尾からのLCS長を求める

$A_R$ と $B$ をそれぞれ反転させてから通常のLCS長DPを行うことで、「末尾から」のLCS長が得られる。

Step 4: 再帰と計算量の関係

よくあるミス

次のステップ

• 発展問題: 編集距離の実際の操作列を同じ考え方で $O(N+M)$ メモリで復元する
• 発展問題: 3つ以上の文字列の最長共通部分列をメモリ効率を意識して求める

自己評価