「Trip」旅行

形式化题目

给定两个字符串 $S_1$ 和 $S_2$ ，字符串仅包含小写字母，长度均不超过 $80$ 。求出这两个字符串的所有不重复的最长公共子序列（Longest Common Subsequence, LCS）。题面要求输出时结果按字典序升序输出，每一个 LCS 占一行，不重复。

正解

思路

本题不仅需要求出最长公共子序列（LCS），还需要按字典序输出所有不重复的 LCS。由于字符串长度较小（ $\le 80$ ），可以使用以下两个步骤：

动态规划求 LCS 长度：使用经典的 DP 计算 LCS 长度。为了方便后续按字典序且从前往后回溯，我们采用后缀 DP，即令 $dp[i][j]$ 表示 $S_1[i \dots n]$ 和 $S_2[j \dots m]$ 的 LCS 长度：
- 若 $S_1[i] == S_2[j]$ ，则 $dp[i][j] = dp[i+1][j+1] + 1$
- 若 $S_1[i] \ne S_2[j]$ ，则 $dp[i][j] = \max(dp[i+1][j], dp[i][j+1])$
预处理字符跳跃表配合 DFS 构造：为了保证天然按字典序生成且能高效去重，避免普通暴力 DFS 产生的指数级重复路径：预处理出两个字符串中，每个位置向后寻找小写字母 a-z 第一次出现的索引（即 nxt1[i][c] 和 nxt2[j][c]）。从 $dp[1][1]$ 开始，枚举待生成的字符 $c \in ['a' \dots 'z']$ ：利用跳转表快速找到 $S_1$ 中的 $ni$ 和 $S_2$ 中的 $nj$ 。若这两个位置依然能够提供所需的 LCS 长度（即 $dp[ni][nj] == \text{剩余长度 } L$ ），则可以将字符 $c$ 拼接到当前结果中，并跳转到 $(ni + 1, nj + 1)$ 递归求解下一级。这种方式既天然满足了字典序，且因为通过跳转表寻找，相同的字符不会在同一次枚举中重复走相同的状态，从而彻底去重。

代码

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
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#!/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-10-09 09:30
# update_at: 2026-10-09 12:52

import sys

ALPHA = 26

type Grid = list[list[int]]   # DP 表 / 字符跳转表，都是「下标 -> 下标」的二维数组


def build_next_table(s: str) -> Grid:
    """nxt[p][c] = 下标 >= p 处第一个字符 c 的位置；不存在记 len(s)。"""
    n = len(s)
    nxt: Grid = [[n] * ALPHA for _ in range(n + 1)]
    for p in range(n - 1, -1, -1):
        for c in range(ALPHA):
            nxt[p][c] = p if ord(s[p]) - 97 == c else nxt[p + 1][c]
    return nxt


def build_lcs_table(a: str, b: str) -> Grid:
    """dp[i][j] = a[i:] 与 b[j:] 的最长公共子序列长度（后缀型）。"""
    n, m = len(a), len(b)
    dp: Grid = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        row, below = dp[i], dp[i + 1]
        for j in range(m - 1, -1, -1):
            row[j] = below[j + 1] + 1 if a[i] == b[j] else max(below[j], row[j + 1])
    return dp


def all_lcs(a: str, b: str) -> list[str]:
    """按字典序返回 a、b 的全部不同最长公共子序列。

    dp 取后缀型，于是可以从前往后拼：每一位按 a~z 挑字符 c，取 c 在两侧的
    首次出现，并要求取完之后两侧剩余部分恰好还能凑出 remain - 1 个字符。
    同一个字符串只有一种走法（每位都取最靠前的那次出现），所以不会重复枚举。
    """
    n, m = len(a), len(b)
    dp = build_lcs_table(a, b)
    nxt_a = build_next_table(a)
    nxt_b = build_next_table(b)
    routes: list[str] = []

    def dfs(pos_a: int, pos_b: int, remain: int, tail: str) -> None:
        """pos_a、pos_b 是两侧下一个可用下标，remain 是还要选的字符数。"""
        if remain == 0:
            routes.append(tail)
            return
        for c in range(ALPHA):
            ia = nxt_a[pos_a][c]
            ib = nxt_b[pos_b][c]
            # 取到 c 之后仍在最优路径上：剩余部分必须还能凑出 remain - 1 个
            if ia < n and ib < m and dp[ia + 1][ib + 1] == remain - 1:
                dfs(ia + 1, ib + 1, remain - 1, tail + chr(97 + c))

    dfs(0, 0, dp[0][0], "")
    return routes              # 逐位按 a~z 枚举 ⇒ 天然字典序，无需再排序


def solve() -> None:
    tokens = sys.stdin.read().split()
    out: list[str] = []
    # 每两行一组「爱丽丝 / 鲍勃」，奇数个 token 时最后一行丢弃
    for a, b in zip(tokens[::2], tokens[1::2]):
        out += all_lcs(a, b)
    if out:
        print("\n".join(out))


if __name__ == "__main__":
    solve()

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
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109/**
 * 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-09 09:30
 * update_at: 2026-10-09 13:30
 */
// 3166 旅行：求两个字符串的【全部不同】最长公共子序列，按字典序升序输出。
// 做法：后缀型 LCS DP + 每个位置「不小于 i 的第一个字符 c」表，
// 在最优路径上按 a~z 枚举跳转 ⇒ 每个不同的 LCS 恰好生成一次（不重不漏）。

#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

const int MAX_LEN = 85;   // 题面单串长度不超过 80
const int ALPHA = 26;

int dp[MAX_LEN][MAX_LEN];   // dp[i][j] = s1[i..n] 与 s2[j..m] 的 LCS 长度，值 <= 80，int 够
ll nxt1[MAX_LEN][ALPHA];    // nxt1[i][c] = 下标 >= i 的第一个字符 c，没有则 n + 1
ll nxt2[MAX_LEN][ALPHA];    // 下标统一用 ll，和 n、m、dfs 的参数保持一致，不做强制转换
char route[MAX_LEN];        // 当前正在拼装的路线
const char LETTER[ALPHA + 1] = "abcdefghijklmnopqrstuvwxyz";
string s1, s2;
ll n, m, lcs_len;

// i、j 是两侧下一个可用下标（1 基），len 是「还要选」的字符数
void dfs(ll i, ll j, ll len) {
    if (len == 0) {
        cout << route << "\n";
        return;
    }
    ll pos = lcs_len - len;    // 本次要填 route 的第 pos 位
    for (int c = 0; c < ALPHA; ++c) {
        ll ni = nxt1[i][c];
        ll nj = nxt2[j][c];
        // 取字符 c 后仍在最优路径上：跳过 c 之后剩下的部分必须正好还能凑出 len - 1 个
        if (ni <= n && nj <= m && dp[ni + 1][nj + 1] == len - 1) {
            route[pos] = LETTER[c];
            dfs(ni + 1, nj + 1, len - 1);
        }
    }
}

void solve() {
    n = s1.length();
    m = s2.length();
    s1 = " " + s1;
    s2 = " " + s2;

    // 后缀型 LCS：s1[i] == s2[j] 时这条匹配必须用上，否则取两侧较大值
    for (int i = 0; i <= n + 1; ++i) {
        for (int j = 0; j <= m + 1; ++j) {
            dp[i][j] = 0;
        }
    }
    for (ll i = n; i >= 1; --i) {
        for (ll j = m; j >= 1; --j) {
            if (s1[i] == s2[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
            } else if (dp[i + 1][j] >= dp[i][j + 1]) {
                dp[i][j] = dp[i + 1][j];
            } else {
                dp[i][j] = dp[i][j + 1];
            }
        }
    }

    lcs_len = dp[1][1];

    // 每个位置往后（含自身）第一个出现的字符，用于 O(1) 跳到下一个候选
    for (int c = 0; c < ALPHA; ++c) {
        nxt1[n + 1][c] = n + 1;
        nxt2[m + 1][c] = m + 1;
    }
    for (ll i = n; i >= 1; --i) {
        for (int c = 0; c < ALPHA; ++c) {
            if (s1[i] - 'a' == c) {
                nxt1[i][c] = i;
            } else {
                nxt1[i][c] = nxt1[i + 1][c];
            }
        }
    }
    for (ll j = m; j >= 1; --j) {
        for (int c = 0; c < ALPHA; ++c) {
            if (s2[j] - 'a' == c) {
                nxt2[j][c] = j;
            } else {
                nxt2[j][c] = nxt2[j + 1][c];
            }
        }
    }

    route[lcs_len] = '\0';
    dfs(1, 1, lcs_len);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    while (cin >> s1 >> s2) {
        solve();
    }
    return 0;
}

复杂度

时间复杂度：
- 动态规划与跳跃表预处理的时间复杂度为 $O(|S_1| \cdot |S_2| + 26 \times (|S_1| + |S_2|))$ 。
- DFS 搜索的时间复杂度正比于答案的数量及每个答案的长度（即输出多项式复杂度）。对于最大的一组测试点生成 $924$ 个答案也是极快完成，因此理论的最坏规模可控，实际表现时间小于 $0.02s$ 。
空间复杂度：
- 存储 DP 状态和跳转表的空间，为 $O(|S_1| \cdot |S_2| + 26 \times (|S_1| + |S_2|))$ 。空间极小，远不达兆级别。

总结

1. 题面与数据不一致（本题启用了 SPJ）

题面明确要求「按升序顺序输出」，并且样例是按照严格字典序排布的（共 7 行，且含 acbca，不缺行）。然而，测试点的真实数据存在极大的缺陷：

在全部 $11$ 个测试点的 .out 文件中，实际输出没有一个是真正的字典序（sorted(ls) == ls 测得 $11/11$ 为 False）。
例如 trip1.out 虽然输出内容集合和样例相同，也是 7 行包含 acbca，但其内部排序极为混乱（acbca 未被排到末尾）。

2. 输出顺序无法复现，强制采用 SPJ

由于数据并不遵守字典序，我们验证了是否能模拟原数据生成程序的输出顺序，但：

尝试了高达 20 个不同机制的 DFS 变体（经典 DFS × 优先匹配边缘 × 前/后缀 DP 等组合）均无法复原这组无规律序列（最高仅匹配 $0/11$ 点）。
使用了 600 个 Python 字典序/Set 哈希 Seed 去进行穷举猜测，也仅碰巧撞上了 trip2。这证明 .out 的顺序属于原题标程未进行任何排序去重的偶发数据，无法被规律复现。这正是本题最终不得不使用 SPJ 进行集合等价判定的核心理由。

3. 代码的 Off-By-One Bug（第一版 Python 存在问题）

在最早编写 Python 实现的 DFS 跳跃算法时，存在一行十分隐蔽但致命的 off-by-one 越界逻辑。

根因：由于预处理数组 nxt1[i][c] 的语义是包含 $i$ 本身以后的下一个字符索引。在回溯跳转时写成了 dfs(ni, nj, ...) 导致它没有越过当前已经选择的字符，使得搜索会在同一级“死循环”或原地踏步，从而丢失大量的解或完全无输出。
应当修复为 dfs(ni + 1, nj + 1, ...)。
V1 单 Token 变异反事实对照：仅仅是将 + 1 去掉的这单一 token 修改。
- 在穷举 $|A|,|B| \le 6$ 的 $15876$ 组全排列对比中，修正版有 $0$ 组不匹配，而错误版有高达 $15474$ 组答案缺损。
- 对于题目的 11 个测试点，修正版全通过，而错误版只有 $2/11$ （且 trip1 的 7 行输出中丢失了 acbaa）。这一事实说明了这个看似无关紧要的步进参数其承重程度极高。

4. SPJ 判据验证与已知局限

SPJ 的工作逻辑并非将用户输出重新排序后简单判断 got == want，而是基于集合正确性的严密校验（行均为合法公共子序列、长度等于 LCS、验证答案集穷尽了所有不同的 LCS）。

通过异源对拍：我们将 SPJ 的校验逻辑与穷举生成 $2^{|A|}$ 子序列的绝对暴力解在高达 $64516$ 组短字符串以及上百组随机用例对撞，得出了 $0$ 分歧，证明 SPJ 判据逻辑极稳。
已知局限：
1. SPJ 内部含有 limit = 2_000_000 兜底保护，如果 LCS 数量过度会保守反馈 FAIL（由于最大的数据测试才 924 行，这几乎不可能被触发）。
2. SPJ 当前只抽取了输入文件的前 2 个 Token，如果测试数据出现多用例的情况，由于 SPJ 逻辑其将忽略后续输入。所幸这 11 组真实用例全为恰好单组。

5. 测试点数据表现与逐点表

| 测试点 | $|A|$ | $|B|$ | LCS $L$ | 输出行数 | main.cpp 与 .out 字节比对 | SPJ 集合对 | main.py 正确性 | main.py 耗时 | Peak RSS | | ------ | ----- | ----- | ------- | -------- | ----------------------------- | ---------- | ---------------- | -------------- | -------- | | trip1 | 8 | 7 | 5 | 7 | ✗ （顺序混乱） | ✅ | ✅ | 0.002 s | 15.6 MB | | trip2 | 8 | 7 | 5 | 7 | ✗ | ✅ | ✅ | 0.002 s | 15.5 MB | | trip3 | 45 | 45 | 39 | 924 | ✗ | ✅ | ✅ | 0.018 s | 15.8 MB | | trip4 | 80 | 80 | 24 | 120 | ✗ | ✅ | ✅ | 0.003 s | 15.6 MB | | trip5 | 60 | 60 | 16 | 120 | ✗ | ✅ | ✅ | 0.003 s | 15.6 MB | | trip6 | 40 | 80 | 18 | 25 | ✗ | ✅ | ✅ | 0.002 s | 15.6 MB | | trip7 | 20 | 80 | 10 | 20 | ✗ | ✅ | ✅ | 0.002 s | 15.6 MB | | trip8 | 40 | 40 | 9 | 207 | ✗ | ✅ | ✅ | 0.002 s | 15.5 MB |

注：因为原题输出不带字典序，所以纯字面比对 $11$ 点全部反馈为 ✗ 失败；SPJ 证明了正解的输出不仅内容准确无误，而且 main.py 最大用时测试点 trip3 (生成了 924 行结果) 耗时仅 $0.018s$ 。

6. 反事实变异对照 (V 系列)

V1 边界变异：去除 + 1 进行 off-by-one 变异，测试导致 $15474$ 个穷举错误，正确反映了其严苛度。
字典序开关对照：如果我们提供一个无排序去重的普通结果序列（存在冗余或者乱序），如果没启动 SPJ，那么因为原题自身没有排序规律直接判错。启动 SPJ 后依然能够兼容此等弱约束，证明 SPJ 对顺序判定极度宽容。
V2 / V4 / V6：
- 输入存在多余的空行或者不可见字符不会干扰使用 cin 及 split() 读取的流程。
- 数据最大 $80$ 的限制，不涉及溢出 long long 也不含有随机化流程，变量上限绝对安全。

7. T9 规范检查表

T9.1 精度与类型：最大值 $LCS$ 极限 $<80$ ，所有中间及记录值皆可使用 int 覆盖，且无乘除带来的进度损失。
T9.2 数组边界保护：数组均依照最大容量 $80$ 余量加成，设定 MAX_LEN=85 并留出后置 +2 安全偏移，不存在 $OOB$ 越界隐患。
T9.3 全局状态复位：针对多用例调用设计，在每一轮使用前均将 DP 数组以及相关逻辑初始化，确保不存在不同数据间相互污染。
T9.4 IO 性能：使用 \n 代替 endl 及开启 C++ 快速 IO；由于最终的打印内容有可能会很大，使用高效单次打印极为必要。
T9.5 模块化设计：核心逻辑与预处理阶段已拆解为独立的 solve() 任务段，回溯通过函数参数传值实现无状态污染递归设计。

「Trip」 旅行

目录