最长公共子序列

概述

最长公共子序列（LCS）问题是给定两个序列 $X$ 和 $Y$，求它们的最长公共子序列的长度和具体序列。该问题是字符串算法的基础问题，广泛应用于文件差异比较（diff工具）和生物信息学（DNA序列比对）等领域。

定义

最长公共子序列（Longest Common Subsequence）

输入：两个序列 $X=⟨x_1,x_2,\dots ,x_m⟩$ 和 $Y=⟨y_1,y_2,\dots ,y_n⟩$。

输出：$X$ 和 $Y$ 的最长公共子序列（LCS）。

设 $c[i,j]$ 为 $X$ 的前缀 $X_i=⟨x_1,\dots ,x_i⟩$ 和 $Y$ 的前缀 $Y_j=⟨y_1,\dots ,y_j⟩$ 的 LCS 长度，则递推公式为： $c[i,j]=\{\begin{array}{ll}0& \text{若 }i=0\text{ 或 }j=0\\ c[i-1,j-1]+1& \text{若 }i,j>0\text{ 且 }{x}_i=y_j\\ \max (c[i-1,j],c[i,j-1])& \text{若 }i,j>0\text{ 且 }{x}_i\ne y_j\end{array}$

核心性质

1. 最优子结构

LCS 的最优子结构体现在以下三种情况：

• 若 $x_m=y_n$，则 $x_m$（或 $y_n$）一定属于某个 LCS，且去掉末尾元素后的 LCS 就是 $X_{m-1}$ 和 $Y_{n-1}$ 的 LCS
• 若 $x_m\ne y_n$ 且 $c[m,n-1]\ge c[m-1,n]$，则 $X_m$ 和 $Y_{n-1}$ 的 LCS 就是 $X_m$ 和 $Y_n$ 的 LCS
• 若 $x_m\ne y_n$ 且 $c[m-1,n]>c[m,n-1]$，则 $X_{m-1}$ 和 $Y_n$ 的 LCS 就是 $X_m$ 和 $Y_n$ 的 LCS

2. 重叠子问题

递归求解 LCS 时，子问题 $(i-1,j)$ 和 $(i,j-1)$ 都会进一步调用 $(i-1,j-1)$，导致大量重复计算。例如，计算 $c[3,3]$ 时，$c[2,2]$ 会被多次访问。

3. 自底向上算法

LCS-LENGTH(X, Y):
    m = X.length
    n = Y.length
    let b[1..m, 1..n] and c[0..m, 0..n] be new tables
    for i = 1 to m:
        c[i,0] = 0
    for j = 0 to n:
        c[0,j] = 0
    for i = 1 to m:
        for j = 1 to n:
            if x_i == y_j:
                c[i,j] = c[i-1,j-1] + 1
                b[i,j] = "↖"      // 左上方向：匹配
            else if c[i-1,j] >= c[i,j-1]:
                c[i,j] = c[i-1,j]
                b[i,j] = "↑"      // 上方：取X的前缀
            else:
                c[i,j] = c[i,j-1]
                b[i,j] = "←"      // 左方：取Y的前缀
    return c and b

4. 构造LCS

通过方向表 $b$ 回溯构造具体的 LCS：

PRINT-LCS(b, X, i, j):
    if i == 0 or j == 0:
        return
    if b[i,j] == "↖":
        PRINT-LCS(b, X, i-1, j-1)
        print x_i
    else if b[i,j] == "↑":
        PRINT-LCS(b, X, i-1, j)
    else:
        PRINT-LCS(b, X, i, j-1)

回溯过程从 $b[m,n]$ 开始，遇到”↖“时输出对应字符，遇到”↑“或”←“时沿对应方向移动，直到到达边界。

5. 空间优化

标准算法的空间复杂度为 $O(mn)$。但注意到计算 $c[i,j]$ 时只需要第 $i-1$ 行和第 $i$ 行的值，因此可以：

• 使用两行数组滚动计算，空间降至 $O(\min (m,n))$
• 若只需要 LCS 长度（不需要构造具体序列），可以进一步优化

复杂度分析

方法	时间复杂度	空间复杂度
朴素递归	$O(2^{\min (m,n)})$	$O(\min (m,n))$
自底向上（标准）	$O(mn)$	$O(mn)$
自底向上（空间优化）	$O(mn)$	$O(\min (m,n))$

应用场景

• diff 工具：Unix/Linux 的 diff 命令基于 LCS 算法比较两个文件的差异
• 版本控制系统：Git 等工具使用 LCS 变体进行代码差异比较
• 生物信息学：DNA/蛋白质序列比对，寻找进化上的保守区域
• 拼写检查：基于编辑距离（与 LCS 密切相关）的纠错建议

章节扩展

• 14.4 最长公共子序列 — LCS 问题的完整求解过程
• 动态规划 — 动态规划完整方法论
• 最优子结构 — 最优子结构性质的详细说明
• 重叠子问题 — 重叠子问题性质的详细说明

参见

• 钢条切割 — 动态规划的入门问题
• 矩阵链乘法 — 另一个经典动态规划问题
• 最优二叉搜索树 — 树结构上的动态规划