困难C++9 分钟3,158 字

最长公共子序列——找出两段文字共有的部分

在生活中,我们经常要比较两段文字或两个序列的相似度。比如老师检查两篇作文有没有抄袭,程序员比较两份代码是不是同一人写的,生物学家比较两段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:

dp 0 a c e
0 0 0 0 0
a 0
b 0
c 0
d 0
e 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,就是最长公共子序列长度。如果想找出具体序列,可以反向回溯(本文最后会提及)。

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

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

cpp
#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入手思考。

同类知识点