公共子序列

题目描述

给定两个长度不超过 200 的字符串，求它们的最长公共子序列长度。输入多组数据，读到文件结束；每组输出一行答案。

思路

$f(i,j)$ 表示两串前缀 $X[1..i]$ 、 $Y[1..j]$ 的 LCS 长度。字符相等时 $f(i,j)=f(i-1,j-1)+1$ ；否则取 $f(i-1,j)$ 与 $f(i,j-1)$ 较大者。用两行滚动数组，并把较短串放内层，空间压到 $O(\min(n,m))$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:53
# update_at: 2026-10-04 11:13

import sys


def lcs_len(x: bytes, y: bytes) -> int:
    """最长公共子序列长度：滚动数组逐位推进，只保留上一行。"""
    # 走短串做行的方向，空间与内层循环长度都取 min(len(x), len(y))。
    if len(x) > len(y):
        x, y = y, x

    prev = [0] * (len(x) + 1)  # 上一行（即以 y 的前 j 个字符为另一个维度的状态）
    for ch in y:
        cur = [0] * (len(x) + 1)  # 当前行；cur[0] 恒为 0，代表空串
        for j, c in enumerate(x, 1):
            if c == ch:
                cur[j] = prev[j - 1] + 1  # 配对成功，接着左上角的最优值
            elif prev[j] > cur[j - 1]:
                cur[j] = prev[j]  # 丢掉 ch，继承上一行同列
            else:
                cur[j] = cur[j - 1]  # 丢掉 c，继承本行左邻
        prev = cur
    return prev[len(x)]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())  # 一次读完，空白切分即可丢掉行尾
    out = []
    while (x := next(data, None)) is not None:  # 题面不给组数，读到 EOF 为止，每两个 token 是一组 (X, Y)
        y = next(data)
        out.append(str(lcs_len(x, y)))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:25
 * update_at: 2026-10-05 08:25
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 205; // 字符串长度上限 200

char x[MAXN], y[MAXN];
int prev_dp[MAXN];    // 上一行 DP 值
int cur_dp[MAXN];     // 当前行 DP 值

// 计算两个字符串的最长公共子序列长度，用滚动数组优化空间。
int lcs_len(char *a, char *b) {
    int n = strlen(a + 1); // a[1..n] 为有效字符
    int m = strlen(b + 1);
    // 让 a 是较短串，内层循环长度取 min(n, m)。
    if (n > m) {
        swap(a, b);
        swap(n, m);
    }
    memset(prev_dp, 0, sizeof(int) * (n + 1));
    for (int i = 1; i <= m; i++) {
        cur_dp[0] = 0; // 第 0 列恒为 0
        for (int j = 1; j <= n; j++) {
            if (b[i] == a[j]) {
                cur_dp[j] = prev_dp[j - 1] + 1; // 配对成功，继承左上角 +1
            } else if (prev_dp[j] > cur_dp[j - 1]) {
                cur_dp[j] = prev_dp[j];         // 丢掉 b[i]
            } else {
                cur_dp[j] = cur_dp[j - 1];      // 丢掉 a[j]
            }
        }
        memcpy(prev_dp, cur_dp, sizeof(int) * (n + 1));
    }
    return prev_dp[n];
}

int main() {
    while (scanf("%s %s", x + 1, y + 1) == 2) {
        printf("%d\n", lcs_len(x, y));
    }
    return 0;
}

目录

题目描述

思路

参考代码