题目描述

爱丽丝和鲍勃想去旅行。

他们每个人制定了一条旅行路线，每条路线包含一个按给定顺序访问的城市列表，一个城市可能会多次出现在同一路线中。

因为他们想要一起去旅行，所以必须在旅行路线上达成一致。

他们两个都不想改变他们的路线上的城市顺序或者在路线上额外添加城市。

因此，他们只能移除各自路线中的一些城市，使得旅行路线达成一致，并且尽可能的长。

该地区共有 26 个城市，用小写字母 a 到 z 表示。

输入格式

输入包含两行，第一行是爱丽丝的路线城市列表，第二行是鲍勃的路线城市列表。

每个列表由 1 到 80 个小写字母组成，其间没有空格。

输出格式

按升序顺序输出所有满足条件的路线列表。

每个路线列表占一行。

样例

abcabcaa
acbacba

ababa
abaca
abcba
acaba
acaca
acbaa
acbca

样例解释

输入

爱丽丝的路线：abcabcaa
鲍勃的路线：acbacba

要求

从两条路线中分别删除一些城市（不能改变剩余城市的顺序），得到两条相同的路线（即公共子序列），并且要求这个公共子序列尽可能长。

输出所有最长公共子序列（可能有多个），按字典序升序输出。

计算最长公共子序列长度

两条序列： A: a b c a b c a a
B: a c b a c b a

最长公共子序列的长度为 5。

所有长度为 5 的公共子序列

我们需要找出所有长度为 5 的公共子序列，并按字典序输出。

根据输出结果，有 7 个：

ababa
abaca
abcba
acaba
acaca
acbaa
acbca

验证：

• ababa：在 A 中取位置 1(a),2(b),4(a),6(b),7(a)；在 B 中取位置 1(a),3(b),4(a),5(c?), 不对，B 中 ababa 对应位置？B: a c b a c b a，取位置 1(a),3(b),4(a),6(b),7(a) → a b a b a，不是 ababa。说明需要仔细匹配。

实际上，公共子序列必须在两个序列中都按顺序出现。我们列举一个： ababa：

• 在 A 中：第 1 个 a，第 2 个 b，第 4 个 a，第 6 个 b，第 7 个 a → a b a b a
• 在 B 中：第 1 个 a，第 3 个 b，第 4 个 a，第 6 个 b，第 7 个 a → a b a b a 匹配成功。

其他类似。

数据范围

• 每条路线长度 1 到 80。
• 城市用小写字母表示（26 种）。

算法分析

这是最长公共子序列（LCS） 问题的变种：需要输出所有最长公共子序列，并按字典序排序。

步骤

1. 计算 LCS 长度。
2. 找出所有 LCS。
3. 排序后输出。

计算 LCS 长度

设 $A[1..n]$, $B[1..m]$。 定义 $dp[i][j]$ 表示 $A[1..i]$ 和 $B[1..j]$ 的 LCS 长度。 转移：

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{if } A[i] = B[j] \\ \max(dp[i-1][j], dp[i][j-1]), & \text{otherwise} \end{cases}$$

找出所有 LCS

使用回溯法，从 $(n,m)$ 开始，根据 $dp$ 值递归构造所有 LCS。

但直接回溯可能会重复，而且数量可能很多（最坏情况指数级），但本题长度最多 80，字母只有 26 种，实际可行。

为了避免重复和效率问题，可以使用记忆化搜索，记录从 $(i,j)$ 开始的所有 LCS 字符串集合。

定义 $f[i][j]$ 为从 $A[i..n]$ 和 $B[j..m]$ 能得到的 LCS 字符串集合（只取最长的，即长度为 $dp[i][j]$）。

转移：

• 如果 $A[i] = B[j]$，则 $f[i][j] = \{ A[i] + s \mid s \in f[i+1][j+1] \}$。
• 否则，如果 $dp[i+1][j] > dp[i][j+1]$，则 $f[i][j] = f[i+1][j]$。
• 如果 $dp[i][j+1] > dp[i+1][j]$，则 $f[i][j] = f[i][j+1]$。
• 如果 $dp[i+1][j] = dp[i][j+1]$，则 $f[i][j] = f[i+1][j] \cup f[i][j+1]$。

注意：为了避免存储大量重复字符串，可以用 set 存储，自动去重。

复杂度

状态数 $O(nm)$，每个状态可能存储多个字符串，但总字符串数量不会超过所有 LCS 的数量，最坏情况可能很大，但实际数据可接受。

最终输出

从 $f[1][1]$ 中得到所有最长公共子序列，排序后输出。

注意事项

• 由于字符串长度最多 80，LCS 长度最多 80，字符串数量可能很多，但题目要求输出所有，且样例输出 7 个，实际可能更多。
• 使用 set 自动排序，最后直接输出即可。
• 注意边界：$i>n$ 或 $j>m$ 时，$f$ 为空集。

另一种优化

由于只需要最长公共子序列，可以在 DP 时同时记录哪些字符可以作为下一个选择，然后从前往后构造，使用 DFS 枚举，并用 DP 值剪枝（确保后面能凑够长度）。

具体：

1. 计算 $dp[i][j]$。
2. 从 $(1,1)$ 开始 DFS，维护当前构造的字符串 $cur$。
3. 在位置 $(i,j)$，如果 $A[i] = B[j]$，且 $dp[i][j] = len(cur) + 1 + dp[i+1][j+1]$，则可以选择 $A[i]$ 作为下一个字符，递归到 $(i+1, j+1)$。
4. 同时，还需要考虑不选 $A[i]$ 或不选 $B[j]$ 的情况，但为了不重复，我们按字典序尝试字符，并跳转到下一个匹配位置。

这种方法可以避免存储大量中间集合，直接输出。

样例验证

对于样例，最长公共子序列长度为 5，所有 LCS 如输出所示。