问题

image-20251116192953141

问题分析

子序列是指从一个序列中删除部分元素（可以不删）后，剩余元素保持原有相对顺序形成的新序列（不要求连续）。

最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

LCS 问题是：给定两个序列（如字符串、数组），找出它们之间长度最长的公共子序列。

例如：

  • 序列 a = "ABCBDAB"，序列 b = "BDCAB"
  • 它们的 LCS 是 "BCAB" 或 "BDAB"，长度为 4。

LCS 的标准解法可以通过动态规划在相对高效的时间内解决

考虑这样的一个状态：

  • 用 二维数组 f[i][j]，表示，序列a的前i个元素与序列b的前j个元素的最长公共子序列长度。

那么现在问题就变成了考察末尾元素 a[i]，b[j] 是否在公共的子序列中

根据 a[i] 和 b[j] 是否相等，分两种情况更新 f[i][j]：

  • 情况 1：a[i] == b[j]（当前字符相同）

    此时这两个字符可以作为 LCS 的一部分，因此 LCS 长度等于前i-1和j-1个元素的 LCS 长度加 1，即：

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

  • 情况 2：a[i] != b[j]（当前字符不同）

    此时 LCS 长度取决于 “去掉a[i]后的子序列” 和 “去掉b[j]后的子序列” 中更长的那个 LCS，即：

    f[i][j] = Math.max(f[i-1][j], f[i][j-1])

那么状态转移方程如下

image-20251116193618807

考虑初始状态：

数组 f 初始化时所有元素为 0，因为空序列与任何序列的 LCS 长度为 0

  • 当 i=0（a为空）时，f[0][j] = 0
  • 当 j=0（b为空）时，f[i][0] = 0

时空复杂度分析

  • 时间复杂度：O(n*m)，其中 n 和 m 是两个序列的长度。双层循环遍历了所有 (n+1)*(m+1) 个状态。
  • 空间复杂度：O(n*m)，由二维数组 f 占用。（可优化为 O(min(n,m))，但你的代码使用了标准解法）。

模板代码

Java

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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();  // 消耗换行符
        String a = " " + scanner.nextLine();  // 字符串 a，前面加一个空格方便从 1 开始索引
        String b = " " + scanner.nextLine();  // 字符串 b，前面加一个空格方便从 1 开始索引

        // 状态dp[i][j] a数组前i个，b数组前j个的最长公共子序列长度
        int[][] f = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i) == b.charAt(j)) {
                    f[i][j] = f[i - 1][j - 1] + 1;    // 如果字符相等，长度加 1
                }else{
                    // 如果字符不等，考虑继承，就是两个数组回到上一个位置的时候，谁的最长公共子序列长，用谁的
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }

        // 输出结果
        System.out.println(f[n][m]);

        scanner.close();
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n, m = map(int, input().split())
a = input().strip()
b = input().strip()
# 前面加空格，方便从1开始索引
a = " " + a
b = " " + b

# 状态数组：f[i][j]表示a前i个字符和b前j个字符的最长公共子序列长度
f = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i] == b[j]:
            f[i][j] = f[i-1][j-1] + 1
        else:
            f[i][j] = max(f[i-1][j], f[i][j-1])

print(f[n][m])

C++

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
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    string a, b;
    getline(cin, a);
    getline(cin, b);
    // 前面加空格，方便从1开始索引
    a = " " + a;
    b = " " + b;
    
    // 状态数组：f[i][j]表示a前i个字符和b前j个字符的最长公共子序列长度
    int f[1001][1001] = {0};  // 假设n和m不超过1000，可根据题目范围调整
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i] == b[j]) {
                f[i][j] = f[i-1][j-1] + 1;
            } else {
                f[i][j] = max(f[i-1][j], f[i][j-1]);
            }
        }
    }
    
    cout << f[n][m] << endl;
    return 0;
}

无重复元素的 LCS 问题

问题分析

当问题中有额外的限制条件时，我们常能发现优化的可能性。

普通的 LCS（最长公共子序列）问题时间复杂度是 O(n*m)（n、m 为两个序列长度），当序列长度很大（比如 1e5）时，这个复杂度会超时。

但如果其中一个序列（比如 X）的元素 无重复，就可以利用这个特性把 LCS 转化为 LIS（最长递增子序列），时间复杂度优化到 O(m log m)（m 为另一个序列长度），效率极大提升。

具体而言，当序列 X 中的元素是唯一的，即串内的每个元素至多出现一次时，LCS 问题可转化为最长递增子序列 LIS 的问题，这样就能实现优化

假设我们有两个序列：

  • X：无重复元素（上面说了 “序列 X 中的元素是唯一的”）
  • Y：可以有重复元素（但我们只关心与 X 共有的元素）

我们的处理逻辑就是：

用 Y 中元素在 X 中的位置，生成一个新序列 Z，然后求 Z 的 LIS 长度，这个长度就是 X 和 Y 的 LCS 长度。

为什么能这样转化？

考虑条件，由于 X 中元素无重复，所以每个元素在 X 中的位置一定是唯一的（例如 X = [a,b,c,d]，a 在 X 中的位置是 1，b 是 2， etc.）。

因此，Y 中能构成 LCS 的元素，在 X 中的位置必然是严格递增的，因为 X 中元素顺序固定。

这意味着：

X 和 Y 的 LCS 长度 = Y 中元素在 X 中位置构成的序列 Z 的 LIS 长度

为什么 Z 的 LIS 就是 LCS？

  • 必要性：若某序列是 X 和 Y 的 LCS，则其元素在 X 中的位置必然递增（因 X 中元素顺序固定），因此对应 Z 的一个递增子序列，故 LCS长度 ≤ LIS 长度。
  • 充分性：若 Z 的某递增子序列长度为 k，则其对应 Y 中的元素在 X 中位置递增，即这些元素在 X 中按顺序出现，因此构成一个公共子序列，故 LIS长度 ≤ LCS长度。

算法步骤

  1. 构建位置映射表

    为 X 中的每个元素记录其位置（索引），由于 X 无重复，可用哈希表（如HashMap）存储，实现 O (1) 查询。

  2. 生成序列 Z

    遍历 Y 中的每个元素：

    • 若该元素在 X 中存在（即存在于映射表中），则将其在 X 中的位置加入 Z；
    • 若不存在，则忽略（因为它不可能属于公共子序列）。

  3. 求 Z 的 LIS 长度

    由于 Z 的 LIS 对应 X 和 Y 中位置递增且元素相同的最长子序列，即 LCS，因此 Z 的 LIS 长度就是答案。

模板代码

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.*;
import java.io.*;

public class LCStoLIS {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 读取序列X和Y的长度（假设X无重复）
        int n = Integer.parseInt(br.readLine()); // X的长度
        int m = Integer.parseInt(br.readLine()); // Y的长度
        
        // 读取序列X，并构建元素到位置的映射（位置从1开始，方便理解）
        int[] X = new int[n];
        Map<Integer, Integer> posMap = new HashMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            X[i] = Integer.parseInt(st.nextToken());
            // 位置=索引+1（避免0值影响）
            posMap.put(X[i], i + 1);
        }
        
        // 生成序列Z：只保留Y中在X出现过的元素，值为其在X中的位置
        List<Integer> Z = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int y = Integer.parseInt(st.nextToken());
            if (posMap.containsKey(y)) {
                Z.add(posMap.get(y));
            }
        }
        
        // 求Z的LIS长度（使用O(m log m)算法）
        System.out.println(lisLength(Z));
    }
    
    // 计算序列的最长递增子序列长度（O(n log n)）
    private static int lisLength(List<Integer> nums) {
        if (nums.isEmpty()) return 0;
        
        // tails[k] 表示长度为 k+1 的递增子序列的最小可能尾部元素
        List<Integer> tails = new ArrayList<>();
        
        for (int num : nums) {
            // 找到tails中第一个 >= num的位置（维持tails递增）
            int idx = Collections.binarySearch(tails, num);
            if (idx < 0) {
                // 转换为插入位置
                idx = -idx - 1;
            }
            // 替换该位置的元素，或追加到末尾
            if (idx == tails.size()) {
                tails.add(num);
            } else {
                tails.set(idx, num);
            }
        }
        return tails.size();
    }
}
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <sstream>
#include <string>

using namespace std;

// 计算序列的最长递增子序列长度（O(n log n)）
int lisLength(const vector<int>& nums) {
    if (nums.empty()) return 0;
    
    vector<int> tails; // tails[k]表示长度为k+1的递增子序列的最小尾部元素
    
    for (int num : nums) {
        // 找到tails中第一个 >= num的位置（使用lower_bound实现）
        auto it = lower_bound(tails.begin(), tails.end(), num);
        int idx = it - tails.begin();
        
        // 替换该位置的元素，或追加到末尾
        if (idx == tails.size()) {
            tails.push_back(num);
        } else {
            tails[idx] = num;
        }
    }
    
    return tails.size();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取序列X和Y的长度（假设X无重复）
    int n, m;
    cin >> n >> m;
    cin.ignore(); // 忽略换行符
    
    // 读取序列X，并构建元素到位置的映射（位置从1开始）
    vector<int> X(n);
    unordered_map<int, int> posMap;
    string line;
    getline(cin, line);
    istringstream issX(line);
    for (int i = 0; i < n; ++i) {
        issX >> X[i];
        posMap[X[i]] = i + 1; // 位置=索引+1
    }
    
    // 生成序列Z：只保留Y中在X出现过的元素，值为其在X中的位置
    vector<int> Z;
    getline(cin, line);
    istringstream issY(line);
    for (int i = 0; i < m; ++i) {
        int y;
        issY >> y;
        if (posMap.count(y)) { // 检查元素是否在X中存在
            Z.push_back(posMap[y]);
        }
    }
    
    // 求Z的LIS长度并输出
    cout << lisLength(Z) << endl;
    
    return 0;
}

例题

题目

P2516 HAOI2010 最长公共子序列 - 洛谷

P2516 [HAOI2010] 最长公共子序列

题目描述

字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列 X = {x0, x1, ⋯, xm − 1}，序列 Y = {y0, y1, ⋯, yk − 1} 是 X 的子序列，当且仅当存在 X 的一个严格递增下标序列 {i0, i1, ⋯, ik − 1} ，使得对所有的 j = 0, 1, ⋯, k − 1 ，有 xij = yj 。例如，$X=\verb!"ABCBDAB"!$ ，$Y=\verb!"BCDB"!$ 是 X 的一个子序列。对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。其中，两个子序列 i 和 j 不同，当且仅当长度不同或子序列中 $\exist k, i_k \neq j_k$。

输入格式

第一行为第一个字符序列，都是大写字母组成，以 . 结束，大写字母个数不超过 5000。

第二行为第二个字符序列，都是大写字母组成，以 . 结束，大写字母个数不超过 5000。

输出格式

第一行输出上述两个最长公共子序列的长度。

第二行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对 108 求余即可。

输入输出样例 #1

输入 #1

1
2
ABCBDAB.
BACBBD.

输出 #1

1
2
4
7

题目分析

首先，这道题是 LCS（最长公共子序列）的进阶问题—— 不仅要计算最长公共子序列的长度，还要统计最长公共子序列的个数（去重后）

核心是在传统 LCS 动态规划的基础上，新增一个 “计数 DP 数组”，并通过容斥原理处理重复计数的问题。

求 LCS 和传统 LCS 问题一致 —— 找到两个序列中 “相对顺序一致、不要求连续” 的最长子序列长度。

例如输入样例中，ABCBDAB 和 BACBBD 的 LCS 长度是 4（如 BCBD、BCAB 等）。

但是额外的需求是要统计所有不同的最长公共子序列的数量，需注意：

  • 两个子序列不同，只要下标选择不同（即使字符序列相同，也算不同）；
  • 答案需对 1e8 取模（避免溢出）。

关键在于去重计数

直接累加可能会重复统计（比如某个子序列可能通过不同路径推导得到），因此需要用容斥原理减去重复计算的部分。

所以我们需要两个 DP 数组，分别处理 “长度” 和 “个数”：

长度 DP 数组：f[i][j]

  • 定义：表示序列 a[1..i]（第一个字符串前 i 个字符）和 b[1..j]（第二个字符串前 j 个字符）的 LCS 长度。
  • 状态转移（和传统 LCS 完全一致）：
    • 若 a[i] == b[j]：当前字符可加入 LCS，f[i][j] = f[i-1][j-1] + 1；
    • 若 a[i] != b[j]：继承之前的最长长度，f[i][j] = max(f[i-1][j], f[i][j-1])。

计数 DP 数组：g[i][j]

  • 定义：表示序列 a[1..i] 和 b[1..j] 中，长度为 f[i][j] 的 LCS 的个数。

那么 g[i][j]的状态转移如何推导？

我们结合 a[i] 和 b[j] 是否相等，以及 f[i][j] 的来源，分情况推导 g[i][j]：

  • 情况 1：a[i] == b[j]（当前字符匹配）

    此时 f[i][j] = f[i-1][j-1] + 1（LCS 长度比左上角多 1）。

    • 能形成当前 LCS 的子序列，必须包含 a[i] 和 b[j]（因为匹配字符是 LCS 的一部分）；
    • 因此，g[i][j] 首先继承 g[i-1][j-1]（所有以 a[i-1] 和 b[j-1] 结尾的 LCS，追加当前字符后形成新的 LCS）。

  • 情况 2：a[i] != b[j]（当前字符不匹配）

    此时 f[i][j] = max(f[i-1][j], f[i][j-1])（LCS 长度来自上方或左方）。

    • 若 f[i][j] == f[i-1][j]：上方状态 (i-1,j) 的所有 LCS 都是当前状态的有效子序列，累加 g[i-1][j]；
    • 若 f[i][j] == f[i-1][j]：上方状态 (i-1,j) 的所有 LCS 都是当前状态的有效子序列，累加 g[i-1][j]；
    • 这其中就需要容斥定理
      • 当a[i] != b[j]，且f[i-1][j] == f[i][j-1] == f[i][j]时：
        • g[i-1][j] 包含了所有以 a[i-1] 和 b[j] 结尾的 LCS；
        • g[i][j-1] 包含了所有以 a[i] 和 b[j-1] 结尾的 LCS；
        • 而 g[i-1][j-1] 中的 LCS 同时被包含在 g[i-1][j] 和 g[i][j-1] 中，导致重复计数，因此需要减去一次。
      • 例如：a=AB，b=BA，当 i=2、j=2 时（a [2]=B，b [2]=A，不匹配）：
        • f[2][2] = max(f[1][2], f[2][1]) = max(1,1) = 1；
        • g[1][2] = 1（来自 a [1]=A 和 b [1..2] 的 LCS 个数）；
        • g[2][1] = 1（来自 a [1..2] 和 b [1]=B 的 LCS 个数）；
        • g[1][1] = 1（重复计数的部分）；
        • 因此 g[2][2] = 1+1-1 = 1（正确，LCS 个数为 1：要么选 A，要么选 B，但长度都是 1，且是同一个 LCS）。

考虑初始状态（边界条件）

  • g[i][0] = 1：任何序列和空序列的 LCS 只有 1 个（空序列本身）；
  • g[0][j] = 1：同理，空序列和任何序列的 LCS 只有 1 个。

Java 内存敏感，就到上面这么写会 MLE

由于 f[i][j] 和 g[i][j] 只依赖于 上一行（i-1） 和 同一行的前一列（j-1），可以用滚动数组将空间复杂度从 O(nm) 优化到 O(m)（n 和 m 是两个序列的长度，最大 5000，O(m) 更节省内存）。

  • 用 f[0][j] 和 f[1][j] 交替存储当前行和上一行的长度；
  • 用 g[0][j] 和 g[1][j] 交替存储当前行和上一行的计数；
  • 用 u 表示当前行的索引（0 或 1），u^1 表示上一行的索引（异或运算快速切换）。
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.util.Scanner;
import java.io.*;

public class Main {

    private static final int N = 5010;
    private static final int MOD = 100000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 读取两个字符串（自动忽略空格，直接读整行）
        String s1 = br.readLine().trim();
        String s2 = br.readLine().trim();

        // 处理字符串：去掉末尾的'.'，从索引1开始存储（方便DP边界处理）
        char[] a = new char[N];
        char[] b = new char[N];
        int n = 0, m = 0;

        // 填充 a 数组（第一个序列）
        for (char c : s1.toCharArray()) {
            if (c == '.') break;
            a[++n] = c; // a[1..n] 为有效字符
        }

        // 填充 b 数组（第二个序列）
        for (char c : s2.toCharArray()) {
            if (c == '.') break;
            b[++m] = c; // b[1..m] 为有效字符
        }

        // 滚动数组：f[0][j] 和 f[1][j] 交替存储当前行和上一行的LCS长度
        int[][] f = new int[2][N];
        // g[0][j] 和 g[1][j] 交替存储当前行和上一行的LCS个数
        int[][] g = new int[2][N];

        // 初始化边界：空序列与任何序列的LCS个数为1
        for (int k = 0; k <= m; k++) {
            g[0][k] = 1;
        }
        g[1][0] = 1;

        int u = 0; // 当前行标记（0或1），u^1 表示上一行
        for(int i = 1; i <= n; i++){
            // 切换行（0 <-> 1）
            u ^= 1;

            for(int j = 1; j <= m; j++){
                // 更新LCS长度（传统LCS逻辑）
                if(a[i] == b[j]){
                    f[u][j] = f[u ^ 1][j - 1] + 1;
                } else {
                    f[u][j] = Math.max(f[u ^ 1][j], f[u][j - 1]);
                }

                // 更新LCS个数（带容斥去重）
                g[u][j] = 0;

                // 情况1：字符匹配，累加左上角计数
                if(a[i] == b[j] && f[u][j] == f[u ^ 1][j - 1] + 1){
                    g[u][j] = (g[u][j] + g[u ^ 1][j - 1]) % MOD;
                }

                // 情况2：长度来自上方，累加上方计数
                if(f[u][j] == f[u ^ 1][j]){
                    g[u][j] = (g[u][j] + g[u ^ 1][j]) % MOD;
                }

                // 情况3：长度来自左方，累加左方计数
                if (f[u][j] == f[u][j - 1]) {
                    g[u][j] = (g[u][j] + g[u][j - 1]) % MOD;
                }

                // 减去重复计数的部分（避免负数）
                if (f[u][j] == f[u ^ 1][j - 1]) {
                    g[u][j] = (g[u][j] - g[u ^ 1][j - 1] + MOD) % MOD;
                }
            }
        }

        // 输出结果（使用 BufferedWriter 提升效率）
        bw.write(f[u][m] + "\n");
        bw.write(g[u][m] + "\n");
        // 刷新缓冲区（必须调用，否则可能不输出）
        bw.flush();

        // 关闭资源
        br.close();
        bw.close();
    }
}
image-20251116205526603