← Back

最长公共子序列（LCS）

最长公共子序列（LCS）

核心结论

最长公共子序列（Longest Common Subsequence，LCS）要求元素的相对顺序保持不变，但不要求它们在原序列中连续。

对长度分别为 m 和 n 的两个序列，经典动态规划算法的时间复杂度为 Θ(mn)\Theta(mn)，空间复杂度为 Θ(mn)\Theta(mn)。

1. 问题定义

给定两个序列：

X=⟨x1,x2,…,xm⟩,Y=⟨y1,y2,…,yn⟩X=\langle x_1,x_2,\ldots,x_m\rangle, \qquad Y=\langle y_1,y_2,\ldots,y_n\rangle

寻找一个最长序列：

Z=⟨z1,z2,…,zk⟩Z=\langle z_1,z_2,\ldots,z_k\rangle

使得 Z 同时是 X 和 Y 的子序列。

1.1 子序列

若存在严格递增的下标序列：

1≤i1<i2<⋯<ik≤m1\le i_1<i_2<\cdots<i_k\le m

使得：

zt=xit,1≤t≤kz_t=x_{i_t}, \qquad 1\le t\le k

则称 Z 是 X 的子序列。

例如，对于 X = ABCBDAB，BCBA 是 X 的子序列，可以依次选择：

B(2) → C(3) → B(4) → A(6)

子序列与子串

  • 子序列只要求相对顺序一致，不要求连续。
  • 子串要求字符在原字符串中连续出现。

2. 基本思想

LCS 具有动态规划的两个典型性质：

  1. 最优子结构：原问题的最优解可以由规模更小的子问题最优解构成。
  2. 重叠子问题：直接递归时，同一对前缀会被重复求解。

考虑两个前缀：

X[1…i]与Y[1…j]X[1\ldots i] \qquad\text{与}\qquad Y[1\ldots j]

比较它们的最后一个元素 xix_i 和 yjy_j。

2.1 当前元素相等

若 xi=yjx_i=y_j，则该元素可以作为当前公共子序列的最后一个元素。

删除这个相同元素后，问题转化为两个更短前缀的 LCS：

c[i][j]=c[i−1][j−1]+1c[i][j]=c[i-1][j-1]+1

2.2 当前元素不相等

若 xi≠yjx_i\ne y_j，则 xix_i 与 yjy_j 不可能同时作为 LCS 的最后一个匹配元素，因此至少要舍弃其中一个：

  • 舍弃 xix_i，得到子问题 c[i−1][j]c[i-1][j]；
  • 舍弃 yjy_j，得到子问题 c[i][j−1]c[i][j-1]。

应保留两种方案中的较优者：

c[i][j]=max⁡{c[i−1][j],c[i][j−1]}c[i][j]=\max\{c[i-1][j],c[i][j-1]\}

3. 状态定义与递推关系

定义：

c[i][j]=∣LCS⁡(X[1…i],Y[1…j])∣c[i][j] = \left| \operatorname{LCS} \bigl(X[1\ldots i],Y[1\ldots j]\bigr) \right|

即，c[i][j]c[i][j] 表示 X 的前 i 个元素与 Y 的前 j 个元素的最长公共子序列长度。

3.1 边界条件

只要有一个前缀为空，公共子序列长度就是 0：

c[i][0]=0,c[0][j]=0c[i][0]=0, \qquad c[0][j]=0

3.2 状态转移方程

c[i][j]={0,i=0 或 j=0,c[i−1][j−1]+1,xi=yj,max⁡{c[i−1][j],c[i][j−1]},xi≠yj.c[i][j]= \begin{cases} 0, & i=0\text{ 或 }j=0,\\[4pt] c[i-1][j-1]+1, & x_i=y_j,\\[4pt] \max\{c[i-1][j],c[i][j-1]\}, & x_i\ne y_j. \end{cases}

记忆方式

  • 当前元素相等：取左上角加 1。
  • 当前元素不相等：取上方和左方的较大值。

4. 具体过程

考虑示例：

X = ABCBDAB
Y = BDCABA

其中 m=7m=7，n=6n=6。

4.1 初始化

创建一个大小为 (m+1)×(n+1)(m+1)\times(n+1) 的二维数组 c。

将第 0 行和第 0 列全部初始化为 0，因为空序列与任意序列的 LCS 长度都为 0。

4.2 按子问题规模填表

按照 i=1,2,…,mi=1,2,\ldots,m 和 j=1,2,…,nj=1,2,\ldots,n 的顺序计算每个状态：

  1. 比较 xix_i 与 yjy_j；
  2. 若相等，使用左上角状态；
  3. 若不相等，比较上方状态和左方状态。

得到动态规划表：

c(i, j)∅BDCABA
∅0000000
A0000111
B0111122
C0112222
B0112233
D0122233
A0122334
B0122344

右下角状态为：

c[7][6]=4c[7][6]=4

所以最长公共子序列的长度为：

4\boxed{4}

5. 从动态规划表回溯

动态规划表给出了 LCS 的长度。要恢复一个具体的 LCS，需要从右下角状态 (m,n)(m,n) 逆向追踪状态转移。

5.1 回溯规则

当前位于状态 (i,j)(i,j)。

规则一：当前元素相等

若 xi=yjx_i=y_j：

  1. 将该元素加入结果；
  2. 向左上角移动到 (i−1,j−1)(i-1,j-1)。

规则二：当前元素不相等

比较：

c[i−1][j]与c[i][j−1]c[i-1][j] \qquad\text{与}\qquad c[i][j-1]
  • 若上方较大，向上移动到 (i−1,j)(i-1,j)，相当于舍弃 xix_i；
  • 若左方较大，向左移动到 (i,j−1)(i,j-1)，相当于舍弃 yjy_j；
  • 若两者相等，两个方向都可能通向某个 LCS。

平局与多解

只要求一个 LCS 时，可以规定固定的平局策略，例如优先向上。

若要求所有 LCS，则需要同时搜索两个方向，并对结果去重。

5.2 本例回溯

约定平局时优先向上。

状态字符比较操作
(7, 6)B ≠ A上、左均为 4，向上
(6, 6)A = A记录 A，向左上
(5, 5)D ≠ B上方较大，向上
(4, 5)B = B记录 B，向左上
(3, 4)C ≠ A左方较大，向左
(3, 3)C = C记录 C，向左上
(2, 2)B ≠ D左方较大，向左
(2, 1)B = B记录 B，向左上

回溯过程中依次记录：

A B C B

由于回溯方向是从序列末尾向前，因此需要反转：

B C B A

所以得到一个最长公共子序列：

BCBA\boxed{\text{BCBA}}

本例的 LCS 不唯一，BCAB 和 BDAB 也都是长度为 4 的最长公共子序列。

6. 伪代码

6.1 构造动态规划表

LCS-LENGTH(X, Y)
   m ← length(X)
   n ← length(Y)

   创建二维数组 c[0..m][0..n]

   for i ← 0 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
         else
            c[i][j] ← max(c[i-1][j], c[i][j-1])

   return c

6.2 回溯恢复一个 LCS

RECONSTRUCT-LCS(X, Y, c)
   i ← length(X)
   j ← length(Y)
   result ← empty list

   while i > 0 and j > 0
      if X[i] = Y[j]
         append X[i] to result
         i ← i - 1
         j ← j - 1

      else if c[i-1][j] ≥ c[i][j-1]
         i ← i - 1

      else
         j ← j - 1

   reverse(result)
   return result

6.3 完整算法

LCS(X, Y)
   c ← LCS-LENGTH(X, Y)
   sequence ← RECONSTRUCT-LCS(X, Y, c)

   return c[length(X)][length(Y)], sequence

7. 正确性要点

7.1 当前元素相等

若 xi=yjx_i=y_j，则存在一个当前前缀的 LCS 以该相同元素结尾。

删除这个末尾元素后，剩余部分必须是两个更短前缀的 LCS，否则可以用更长的公共子序列替换它，从而与当前解的最优性矛盾。

因此：

c[i][j]=c[i−1][j−1]+1c[i][j]=c[i-1][j-1]+1

7.2 当前元素不相等

若 xi≠yjx_i\ne y_j，则任意公共子序列不可能同时以这两个不同元素结尾。

因此，一个最优解至少满足以下情况之一：

  • 不使用 xix_i；
  • 不使用 yjy_j。

于是：

c[i][j]=max⁡{c[i−1][j],c[i][j−1]}c[i][j]=\max\{c[i-1][j],c[i][j-1]\}

这两个分支覆盖了所有可能的最优解。

8. 时间与空间复杂度

设两个序列的长度分别为 m 和 n。

8.1 时间复杂度

动态规划表共有 (m+1)(n+1)(m+1)(n+1) 个状态，每个状态只进行常数次操作，因此填表时间为：

Θ(mn)\Theta(mn)

回溯过程中，每一步至少使 i 或 j 减少 1，所以回溯时间为：

O(m+n)O(m+n)

总时间复杂度由填表阶段主导：

Θ(mn)\boxed{\Theta(mn)}

8.2 空间复杂度

保存完整动态规划表需要：

Θ(mn)\boxed{\Theta(mn)}

若只求 LCS 长度，可以使用滚动数组，将空间复杂度优化为：

Θ(min⁡(m,n))\boxed{\Theta(\min(m,n))}

空间优化的限制

普通滚动数组不会保存完整的状态转移路径，因此不能直接用于回溯恢复具体 LCS。

若希望在线性空间内恢复 LCS，可以进一步学习 Hirschberg 算法。

9. 与最长公共子串的区别

对比项最长公共子序列最长公共子串
是否要求连续否是
当前元素相等左上角加 1左上角加 1
当前元素不相等取上方、左方最大值置 0
最终答案位置右下角状态整张表的最大值
本例结果BCBA 等AB 或 BD

详见 最长公共子串。

10. 易错点

  • 混淆子序列与子串：子序列不要求连续，子串必须连续。
  • 字符不等时向左上移动：字符不等时只能根据上方和左方状态决定方向。
  • 将整张表最大值当作答案：LCS 的答案是右下角状态 c[m][n]c[m][n]。
  • 回溯后忘记反转：回溯得到的字符顺序与最终 LCS 相反。
  • 认为 LCS 必然唯一：平局状态可能对应多个不同的 LCS。
  • 使用滚动数组后仍直接回溯：滚动数组没有保存完整路径。

一句话总结

当前元素相等时，选择该元素并向左上移动；当前元素不相等时，沿着较大的状态向上或向左移动。

11. 关联笔记

  • 动态规划
  • 最长公共子串
  • Hirschberg 算法

12. 参考资料

  • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms, 3rd ed., Section 15.4, “Longest Common Subsequence”.
  • Erik D. Demaine and Charles E. Leiserson. Introduction to Algorithms, Lecture 12: Dynamic Programming, 2005.
  • 课程讲义：lec12.pdf