線性空間計算最長公共子序列：Hirschberg 算法深度解析

編輯：關於C語言

最長公共子序列（LCS）是經典動態規劃問題。傳統 DP 算法雖時間複雜度為 O(mn)，但空間複雜度同為 O(mn)，對長字串（如 DNA 序列、大型文本比對）極不友好。1975 年，D.S. Hirschberg 提出線性空間 LCS 算法，將空間降至 O(min(m,n))，且時間仍保持 O(mn)，成為後續所有線性空間序列比對算法的基石。

問題背景與動機

對長度 10,000 的字串，傳統 DP 需 100M 空間（約 100 MB），在 1975 年甚至當今嵌入式環境均難以承受。Hirschberg 算法僅需約 100 KB，使大規模序列比對成為可能。

核心概念定義

子序列：字串 C 為 A 的子序列，若存在嚴格遞增映射 F 使 C[i] = A[F(i)]。
公共子序列：同時是 A 和 B 的子序列。
LCS：長度最大的公共子序列。
L(i,j)：A[1..i] 與 B[1..j] 的 LCS 長度。
D_k:t：字串 D 從 k 到 t 的子串（k≤t 正向，k>t 逆向）。

傳統 DP 算法（算法 A）回顧

for i = 1 to m:
    for j = 1 to n:
        if A[i] == B[j]:
            L[i][j] = L[i-1][j-1] + 1
        else:
            L[i][j] = max(L[i][j-1], L[i-1][j])

此算法需完整 m×n 矩陣，空間 O(mn)。

Hirschberg 算法核心思想：分治 + 空間優化

關鍵洞見：計算 L(i,j) 僅依賴前一行。若只求 LCS 長度，只需兩行滾動數組，空間 O(min(m,n))。但要重構 LCS 本身，需知道決策路徑。

Hirschberg 算法採用分治策略：

將字串 A 對半分：A = A_left + A_right。
正向計算 A_left 與 B 的 LCS 長度數組（僅保留最後一行）。
逆向計算 A_right 與 B 的 LCS 長度數組（僅保留最後一行）。
找到 B 中的最佳分割點 k，使正向長度 + 逆向長度最大。
遞歸求解 (A_left, B[1..k]) 和 (A_right, B[k+1..n])。
合併結果得到完整 LCS。

空間複雜度分析

每層遞歸僅需 O(n) 空間存儲兩行 DP 數組。
遞歸深度 O(log m)，總空間 O(n log m)。
若迭代實現（手動棧），可進一步優化至 O(n)。

Python 參考實現

def lcs_linear_space(A, B):
    if not A or not B:
        return ""
    if len(A) == 1:
        return A if A in B else ""
    if len(B) == 1:
        return B if B in A else ""
    
    mid = len(A) // 2
    A_left, A_right = A[:mid], A[mid:]
    
    # 正向 DP
    def forward_dp(X, Y):
        dp = [0] * (len(Y) + 1)
        for x in X:
            prev = 0
            for j, y in enumerate(Y, 1):
                temp = dp[j]
                if x == y:
                    dp[j] = prev + 1
                else:
                    dp[j] = max(dp[j], dp[j-1])
                prev = temp
        return dp
    
    L1 = forward_dp(A_left, B)
    L2 = forward_dp(A_right[::-1], B[::-1])
    
    # 找最佳分割點
    max_val, split = -1, 0
    for j in range(len(B) + 1):
        val = L1[j] + L2[len(B) - j]
        if val > max_val:
            max_val, split = val, j
    
    return (lcs_linear_space(A_left, B[:split]) + 
            lcs_linear_space(A_right, B[split:]))