一、算法概述

最长公共子序列（Longest Common Subsequence, LCS）是指在两个序列中，找到它们共同拥有的最长的子序列。子序列不要求在原序列中连续，但要求保持相对顺序。

例如：

• 序列 ABCDGH 和 AEDFHR 的 LCS 是 ADH，长度为 3。
• 序列 AGGTAB 和 GXTXAYB 的 LCS 是 GTAB，长度为 4。

LCS 是经典的动态规划问题，也是许多字符串/序列比较问题（如 diff 工具、DNA 序列比对）的基础。

---

二、核心思想

定义 dp[i][j] 表示 s1 的前 i 个字符与 s2 的前 j 个字符的最长公共子序列长度。

状态转移方程：

• 若 s1[i-1] == s2[j-1]，则该字符一定在 LCS 中：

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

• 若 s1[i-1] != s2[j-1]，则至少有一个字符不在 LCS 中：

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

回溯输出 LCS 内容： 从 dp[n][m] 开始，逆向推导：

• 若 s1[i-1] == s2[j-1]，则该字符属于 LCS，记录并移动到 dp[i-1][j-1]
• 否则，移动到 dp[i-1][j] 和 dp[i][j-1] 中较大的那个方向

---

三、算法步骤 / 伪代码

输入: 字符串 s1 (长度 n), 字符串 s2 (长度 m)
输出: LCS 的长度和具体内容

1. 初始化 dp[n+1][m+1] 全为 0
2. for i = 1 to n:
       for j = 1 to m:
           if s1[i-1] == s2[j-1]:
               dp[i][j] = dp[i-1][j-1] + 1
           else:
               dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3. LCS 长度 = dp[n][m]

4. 回溯构造 LCS:
       i = n, j = m, lcs_str = ""
       while i > 0 and j > 0:
           if s1[i-1] == s2[j-1]:
               lcs_str = s1[i-1] + lcs_str
               i--, j--
           else if dp[i-1][j] > dp[i][j-1]:
               i--
           else:
               j--
       返回 lcs_str

---

四、C++ 代码实现

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

int main() {
    string s1, s2;
    cout << "请输入第一个序列: ";
    cin >> s1;
    cout << "请输入第二个序列: ";
    cin >> s2;

    int n = s1.length(), m = s2.length();

    // dp[i][j] 表示 s1[0..i-1] 与 s2[0..j-1] 的 LCS 长度
    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 (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    int lcsLength = dp[n][m];
    cout << "LCS 长度: " << lcsLength << endl;

    // 回溯输出 LCS 内容
    string lcs;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            lcs = s1[i - 1] + lcs; // 逆序拼接，所以加在前面
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    cout << "LCS 内容: " << lcs << endl;

    // ============ 打印 DP 表（调试用） ============
    cout << "\nDP 表:" << endl;
    cout << "    ";
    for (int j = 0; j < m; j++) cout << s2[j] << " ";
    cout << endl;
    for (int i = 0; i <= n; i++) {
        if (i == 0) cout << "  ";
        else cout << s1[i - 1] << " ";
        for (int j = 0; j <= m; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

---

五、复杂度分析

指标	复杂度	说明
时间复杂度	O(n × m)	两层循环填表，n、m 分别为两序列长度
空间复杂度		DP 表大小为 (n+1) × (m+1)
空间优化	O(min(n, m))	可使用滚动数组（两行），因为 dp[i] 只依赖 dp[i-1] 和 dp[i]

空间优化思路： 由于 dp[i][j] 只依赖 dp[i-1][j-1]、dp[i-1][j] 和 dp[i][j-1]，可以用两行（prev[0..m] 和 cur[0..m]）来逐行更新，将空间降到 O(m)。若需要回溯输出 LCS 内容，则不能优化空间（需保留完整 DP 表）。

---

六、应用场景

1. 文件差异比较（Diff 工具）： diff 命令、Git 差异比较的底层原理
2. DNA / 基因序列比对： 生物信息学中比较两段基因的相似度
3. 版本控制： 比较两个版本的代码，找出公共部分和差异
4. 论文查重 / 代码查重： 用 LCS 计算两段文本的相似度
5. 拼写检查： 计算输入词与词典词的相似度
6. 语音识别： 比较识别结果与候选文本

---

七、经典例题

LeetCode 1143. 最长公共子序列

题目描述： 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。

解题代码：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.length(), m = text2.length();
        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 (text1[i - 1] == text2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }
};

空间优化版（O(min(n,m)) 空间）：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // 让 text2 成为较短的那个，优化空间
        if (text1.length() < text2.length())
            swap(text1, text2);
        int n = text1.length(), m = text2.length();

        vector<int> prev(m + 1, 0), cur(m + 1, 0);

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1[i - 1] == text2[j - 1])
                    cur[j] = prev[j - 1] + 1;
                else
                    cur[j] = max(prev[j], cur[j - 1]);
            }
            swap(prev, cur);
        }
        return prev[m];
    }
};