最长公共子序列

一句话算法

LCS 把两个字符串的前缀配成一张表：末尾相等就一起收下，末尾不等就丢掉其中一个末尾。

问题模型

给定两个字符串 $a$ 和 $b$，求它们的最长公共子序列长度。

子序列可以删除若干字符，但不能改变剩余字符的相对顺序。例如：

• ace 是 abcde 的子序列；
• aec 不是 abcde 的子序列，因为相对顺序变了。

公共子序列必须同时是两个字符串的子序列。LCS 要求在所有公共子序列中找长度最大的一个。

核心直觉

考虑两个前缀：

a[1..i]
b[1..j]

真正影响下一步判断的是两个前缀的末尾字符：

a[1..i-1]  a[i]
b[1..j-1]  b[j]

如果 a[i] == b[j]，这两个末尾字符可以作为公共子序列的最后一个字符，于是答案来自左上角：

dp[i - 1][j - 1] + 1

如果 a[i] != b[j]，它们不能同时作为最后一个匹配字符。此时至少要丢掉一个末尾：

丢 a[i]：dp[i - 1][j]
丢 b[j]：dp[i][j - 1]

取更大的那个。

状态设计

定义：

表示 a 的前 $i$ 个字符和 b 的前 $j$ 个字符的最长公共子序列长度。

边界：

因为任意字符串和空串的公共子序列长度都是 $0$。

状态转移

当两个末尾字符相等：

可以把这个字符接在 a[1..i-1] 与 b[1..j-1] 的 LCS 后面：

当两个末尾字符不相等：

最长公共子序列不可能同时使用这两个末尾字符，所以转移为：

合并写法：

算法步骤

1. 读入两个字符串 a 和 b。
2. 建立大小为 (n + 1) * (m + 1) 的 dp 表。
3. 从 i = 1 到 n 枚举 a 的前缀。
4. 从 j = 1 到 m 枚举 b 的前缀。
5. 如果 a[i - 1] == b[j - 1]，从左上角加一转移。
6. 否则从上方和左方取最大值。
7. dp[n][m] 就是答案。

算法证明

核心不变量：处理完格子 $(i,j)$ 后，dp[i][j] 等于 a 的前 $i$ 个字符和 b 的前 $j$ 个字符的 LCS 长度。

1. 边界正确

   如果 $i=0$ 或 $j=0$，其中一个前缀为空，不可能选出非空公共子序列，所以答案是 $0$。

2. 末尾相等时转移正确

   当 $a_i=b_j$ 时，可以把这个相同字符放到公共子序列末尾。

   直觉模型是：两个末尾字符已经对上了，剩下的问题只在它们左边。

   $$LCS(a[1..i],b[1..j]) = LCS(a[1..i-1],b[1..j-1]) + a_i$$

   因此长度为：

   $$dp[i-1][j-1]+1$$

3. 末尾不等时转移正确

   当 $a_i \ne b_j$ 时，最长公共子序列的最后一次匹配不可能同时使用 $a_i$ 和 $b_j$。

   因此它只能属于下面两类之一：

   • 不使用 $a_i$，长度不超过 $dp[i-1][j]$；
   • 不使用 $b_j$，长度不超过 $dp[i][j-1]$。

   两类都覆盖了所有可能情况，所以取最大值：

   $$dp[i][j]=\max(dp[i-1][j],dp[i][j-1])$$

4. 计算顺序正确

   dp[i][j] 只依赖左上、上方、左方三个已经计算过的格子。按行从小到大枚举时，依赖总是已知。

因此算法正确。

复杂度分析

设两个字符串长度分别为 $n$ 和 $m$。

• 时间复杂度：$O(nm)$，每个状态只计算一次。
• 空间复杂度：$O(nm)$，保存完整二维表。

如果只求长度，可以用滚动数组把空间优化到 $O(m)$；如果要还原具体序列，通常保留二维表更直接。

代码实现

求 LCS 长度：

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

        #include <bits/stdc++.h>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;

    int n = a.size();
    int m = b.size();

    // dp[i][j]: a 的前 i 个字符与 b 的前 j 个字符的 LCS 长度。
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[n][m] << "\n";
    return 0;
}
    

还原任意一个 LCS：

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

        #include <bits/stdc++.h>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;

    int n = a.size();
    int m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    string ans;
    int i = n;
    int j = m;
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            ans.push_back(a[i - 1]);
            i--;
            j--;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    reverse(ans.begin(), ans.end());

    cout << dp[n][m] << "\n";
    cout << ans << "\n";
    return 0;
}
    

测试用例

输入：

abcde ace

输出：

3

解释：ace 是两个字符串的公共子序列，长度为 3。

使用还原模板时，输出为：

3
ace

应用分类详解

LCS 的本质是：两个序列按相对顺序匹配，允许跳过元素，问最多能匹配多少个位置。只要题目强调“保留相对顺序”“删除若干元素”“两个序列变得相同”，就应该想到 LCS 或它的变形。

一、两个序列的最长共同模式

典型模式： 给两个字符串或数组，要求最长的共同子序列。

识别信号： 出现“子序列”“不要求连续”“保持原顺序”“最长公共部分”。

核心建模： dp[i][j] 表示两个前缀的最优匹配长度，末尾相等时一起收下，末尾不等时跳过一个末尾。

二、最少删除使两个序列相同

典型模式： 每次只能删除字符，问最少删除多少次让两个字符串相同。

识别信号： 操作只有删除，目标是两个序列最后一致。

核心建模： 最后保留下来的共同部分越长，删除次数越少。

如果 LCS 长度为 $L$，两个字符串长度分别为 $n,m$，则最少删除次数是：

三、编辑距离的前置模型

典型模式： 题目允许插入、删除、替换等操作，把一个字符串变成另一个字符串。

识别信号： 出现“最少操作次数”“字符串转换”“插入删除替换”。

核心建模： LCS 只处理“匹配或跳过”，编辑距离在此基础上给不同操作设置代价。

四、路径还原与方案输出

典型模式： 不只问长度，还要求输出一个最长公共子序列。

识别信号： 输出“一个方案”“任意一种最长序列”“路径”。

核心建模： 从 dp[n][m] 倒着走：相等走左上并记录字符，否则走向值更大的相邻状态。

经典例题

1. roj-1265

LCS 模板题。重点是理解 dp[i][j] 的含义：两个前缀之间最多能匹配多少个字符。

2. LeetCode 1143

标准最长公共子序列。适合练习二维 DP 表和边界处理。

3. luogu-P1439

两个排列的最长公共子序列。直接做 LCS 是 $O(n^2)$，当 $n$ 很大时需要把一个排列映射成位置序列，再转成 LIS。

4. luogu-P2758

编辑距离。它和 LCS 一样使用两个前缀作为状态，但转移中加入插入、删除、替换三类操作，是 LCS 模型的自然扩展。

参考

• 本文旧版解析保留的核心思路：用两个前缀的末尾字符分类讨论。
• CLRS: Dynamic Programming, Longest Common Subsequence.