最长公共子序列——找出两段文字共有的“隐形线索”

在生活中，我们经常要比较两段文字或两个序列的相似度。比如老师检查两篇作文有没有抄袭，程序员比较两份代码是不是同一人写的，生物学家比较两段DNA是否来自同一祖先。所有这些场景，都用得到“最长公共子序列”（Longest Common Subsequence，简称LCS）。

简单来说，给定两个字符串，我们要找出它们最长的、公共的、并且保持各自顺序不变的子序列。注意：子序列不要求连续，只要求顺序一致。比如“abcde”和“ace”，它们的公共子序列有“a”、“c”、“e”、“ac”、“ae”、“ce”，最长的是“ace”，长度为3。

接下来，我们就一步步掌握如何用动态规划求解最长公共子序列的长度，并且知道它具体是哪几个字符。

什么是子序列？和子串有什么区别？

• 子串（substring）：必须是原字符串中连续的一段。比如“abcde”的子串有“abc”、“cd”、“bcd”等，但“ace”不是子串，因为a和c中间隔了b，不连续。
• 子序列（subsequence）：不要求连续，只要按原顺序挑出字符即可。比如“abcde”的子序列有“a”、“b”、“c”、“d”、“e”、“ab”、“ac”、“ad”……也包括“ace”。

很多同学容易搞混，记住口诀：子串是连续的，子序列可以跳着选。

动态规划思路：填一张二维表格

我们不需要真的枚举所有子序列（那样太慢），而是用动态规划把问题分解成小问题。

定义状态

让 dp[i][j] 表示：字符串A的前 i 个字符 和 字符串B的前 j 个字符 的最长公共子序列长度。

举例：A = "abcde"，B = "ace"
dp[3][2] 表示 A 的前3个字符 "abc" 和 B 的前2个字符 "ac" 的最长公共子序列长度，结果是 "ac"，长度2。

递推规则（重点）

当我们计算 dp[i][j] 时，有两种情况：

1. 最后一个字符相等：如果 A[i-1] == B[j-1]（因为C++下标从0开始，所以第i个字符下标是i-1），那么这个字符一定可以加进公共子序列里。于是 dp[i][j] = dp[i-1][j-1] + 1。

2. 最后一个字符不等：这时候 A[i-1] 和 B[j-1] 不可能同时出现在最长公共子序列中。那么最长公共子序列要么来自 dp[i-1][j]（舍弃A的第i个字符），要么来自 dp[i][j-1]（舍弃B的第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]);

初始化

dp[0][j] 表示A是空串，最长公共子序列长度肯定是0。
dp[i][0] 表示B是空串，长度也是0。
所以我们把 dp 的初始值全部设为0，从第1行第1列开始填。

生活例子：零花钱购买计划

为了帮助理解，我们换一个生活中的例子。假设小明每个月有零花钱，他计划买两种零食：

• 零食清单A（按时间顺序）：薯片，饼干，巧克力，糖果，果冻
• 零食清单B（按口味偏好顺序）：薯片，巧克力，果冻，饼干

他想找出既在A中出现过、又在B中出现过，并且顺序不能乱的“共同购买计划”。这个共同计划就是一个公共子序列。最长公共子序列是“薯片，巧克力，果冻”或者“薯片，饼干，果冻”（顺序必须和两个清单都一致）。动态规划表格就是一步步决策：当前这个零食要不要选进去。

一步一步推演表格

我们用A = "abcde"，B = "ace" 来手动填表，加深理解。

先画一个 (n+1) x (m+1) 的表格，n=5，m=3。行表示A的前缀（0到5），列表示B的前缀（0到3）。

初始时全部行和列（下标0）都是0：

现在逐行逐列计算。i从1到5，j从1到3。

• i=1（A[i-1]=‘a’）：
  • j=1：B[0]=‘a’，相等 → dp[1][1] = dp[0][0] + 1 = 1
  • j=2：B[1]=‘c’，不相等 → max(dp[0][2], dp[1][1]) = max(0, 1) = 1
  • j=3：B[2]=‘e’，不相等 → max(dp[0][3], dp[1][2]) = max(0, 1) = 1
• i=2（A[i-1]=‘b’）：
  • j=1：不相等 → max(dp[1][1], dp[2][0]) = max(1, 0) = 1
  • j=2：不相等 → max(dp[1][2], dp[2][1]) = max(1, 1) = 1
  • j=3：不相等 → max(dp[1][3], dp[2][2]) = max(1, 1) = 1
• i=3（A[i-1]=‘c’）：
  • j=1：不相等 → max(dp[2][1], dp[3][0]) = max(1, 0) = 1
  • j=2：相等 → dp[3][2] = dp[2][1] + 1 = 2
  • j=3：不相等 → max(dp[2][3], dp[3][2]) = max(1, 2) = 2
• i=4（A[i-1]=‘d’）：
  • j=1：不相等 → 1
  • j=2：不相等 → max(dp[3][2], dp[4][1]) = max(2, 1)=2
  • j=3：不相等 → max(dp[3][3], dp[4][2]) = max(2, 2)=2
• i=5（A[i-1]=‘e’）：
  • j=1：不相等 → 1
  • j=2：不相等 → max(dp[4][2], dp[5][1]) = max(2, 1)=2
  • j=3：相等 → dp[5][3] = dp[4][2] + 1 = 3

最后的 dp[5][3]=3，就是最长公共子序列长度。如果想找出具体序列，可以反向回溯（本文最后会提及）。

完整代码演示（保留原始 + 输出具体序列）

下面的代码不仅输出长度，还能通过回溯打印出其中一个最长公共子序列。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string A = "abcde";    // 字符串A
    string B = "ace";      // 字符串B
    int n = A.size(), m = B.size();
    
    // dp大小为 (n+1) x (m+1)，初始全0
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    
    // 填dp表
    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] << endl;
    
    // 回溯找出一个LCS字符串
    string lcs = "";
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (A[i-1] == B[j-1]) {
            lcs = A[i-1] + lcs;   // 从后往前加
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;    // 往上走
        } else {
            j--;    // 往左走
        }
    }
    cout << "其中一个最长公共子序列是: " << lcs << endl;
    
    return 0;
}

运行结果：

最长公共子序列的长度是: 3
其中一个最长公共子序列是: ace

常见错误与调试技巧

1. 下标混淆：dp[i][j] 对应的是 A 的前 i 个（下标0到i-1）和 B 的前 j 个。在比较 A[i-1] 和 B[j-1] 时，很多同学写成 A[i] 和 B[j]，导致越界或结果错误。记住：dp[i][j] 的 i 和 j 是从1开始的，而字符串下标是从0开始的。

2. 忘记初始化：vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); 已经初始化全0，但如果是手动开的数组，记得把第0行第0列全部设为0。

3. 子序列和子串混用：如果题目要求的是“子串”（连续），动态规划方法完全不同（要用 dp[i][j] 表示以当前字符结尾的最长公共子串长度）。一定看清题目是“子序列”还是“子串”。

4. 回溯时只找了一种结果：最长公共子序列可能不止一个，回溯只按一种策略（优先向上或向左）会得到一个解，如果想找所有解，需要用更复杂的方法。

总结与相关知识点

• 最长公共子序列 是动态规划的经典题目，核心思想是：当前字符匹配就加1，不匹配就取两个方向的最大值。
• 时间复杂度 O(nm)，空间复杂度 O(nm)，可以优化成 O(min(n,m)) 的一维数组，但通常二维表格更直观。
• 学习LCS后，可以继续探索：
  • 最长公共子串（用不同DP定义）
  • 编辑距离（Levenshtein distance，与LCS很相似）
  • 最长递增子序列（LIS，可以用类似思维）
  • 序列比对（生物信息学中的Needleman-Wunsch算法）

掌握LCS，你就掌握了动态规划中“序列匹配”类问题的基本模式。以后遇到任何需要比较两个序列相似度的问题，都可以先从LCS入手思考。