1092. 最短公共超序列

发表于 分类于 阅读次数： Waline： 本文字数： 987 阅读时长 ≈ 3 分钟

考点

  • LCS
  • SCS

思路

一、问题描述

给定两个字符串 \[ \text{str}_1,\ \text{str}_2 \] 要求构造一个最短的字符串 \(S\)，使得：

  • \(\text{str}_1\) 是 \(S\) 的子序列
  • \(\text{str}_2\) 是 \(S\) 的子序列

该字符串 \(S\) 称为 最短公共超序列（Shortest Common Supersequence, SCS）。

二、问题的本质：长度分析视角

设：

  • \(|\text{str}_1| = n_1\)
  • \(|\text{str}_2| = n_2\)
  • 最终答案长度为 \(|S| = \text{len}\)

1. 最坏情况

若两个字符串完全没有任何可共享的子序列， 则只能将二者直接拼接： \[ \text{len} = n_1 + n_2 \] 这是显然的上界。

2. 可共享子序列带来的“压缩”

若两个字符串中存在某些公共子序列， 则这些字符在构造 \(S\) 时不必重复出现，可以“合并”为一次。

设：

  • 在最终构造的超序列中，被“合并”的公共部分总长度为 \(k\)

则： \[ \text{len} = n_1 + n_2 - k \] 因此：

要最小化最终长度 \(\text{len}\)，等价于最大化可以合并的公共子序列长度 \(k\)。

3. 为什么 \(k\) 的最大值就是 LCS？

任何被“合并”的字符集合，都必须满足：

  • 它是 \(\text{str}_1\) 的子序列
  • 同时也是 \(\text{str}_2\) 的子序列

因此，所有可被合并的字符，本质上构成了一个公共子序列。

而其中长度最大的，正是： \[ k_{\max} = \mathrm{LCS}(\text{str}_1, \text{str}_2) \] 由此得到结论： \[ \boxed{ |\mathrm{SCS}| = n_1 + n_2 - \mathrm{LCS}(\text{str}_1, \text{str}_2) } \]

重要澄清： 这并不意味着“删掉 LCS 后就不存在其它公共子序列”。 而是：

在任意公共超序列中，最多只能合并 \(\mathrm{LCS}\) 长度那么多的字符。

三、算法设计思路

问题分为两个阶段：

  1. 计算 LCS 的长度（DP）
  2. 在 LCS 的 DP 表上回溯，构造一个实际的 SCS

四、阶段一：LCS 动态规划

状态定义

\[ f[i][j] = \text{str}_1[0..i-1] \text{ 与 } \text{str}_2[0..j-1] \text{ 的 LCS 长度} \]

状态转移

\[ f[i][j] = \begin{cases} f[i-1][j-1] + 1, & \text{if } \text{str}_1[i-1] = \text{str}_2[j-1] \\ \max(f[i-1][j], f[i][j-1]), & \text{otherwise} \end{cases} \]

边界条件

\[ f[0][*] = f[*][0] = 0 \]

五、阶段二：从 LCS 表中恢复最短公共超序列

构造字符串本身的关键在于： 沿着 LCS 的决策路径反向回溯。

从 \((i, j) = (n_1, n_2)\) 出发：

回溯规则

  1. 字符相等 \[ \text{str}_1[i-1] = \text{str}_2[j-1] \]

    • 该字符属于 LCS，可被共享
    • 加入答案一次
    • 同时移动 \(i--, j--\)

  2. 字符不等

    • 若 \(f[i-1][j] \ge f[i][j-1]\)
      • LCS 决策来自上方
      • 当前字符只能来自 \(\text{str}_1\)
    • 否则
      • 当前字符只能来自 \(\text{str}_2\)

  3. 某一字符串已走完

    • 另一字符串剩余部分只能全部追加

由于是从后向前构造，最终需要反转结果字符串。

六、AC代码

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
class Solution {
public:
    static const int maxn = 1e3 + 5;

    string shortestCommonSupersequence(string str1, string str2) {
        int f[maxn][maxn];
        memset(f, 0, sizeof(f));

        int n1 = str1.size(), n2 = str2.size();

        // ---------- Phase 1: LCS DP ----------
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (str1[i - 1] == str2[j - 1]) {
                    // 当前字符可以作为公共子序列的一部分
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    // 取删除其中一个字符后的最优解
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }

        // ---------- Phase 2: 回溯构造 SCS ----------
        string res;
        int i = n1, j = n2;

        while (i > 0 && j > 0) {
            if (str1[i - 1] == str2[j - 1]) {
                // 字符相同：属于 LCS，可共享，只加入一次
                res += str1[i - 1];
                --i;
                --j;
            } else {
                // 根据 LCS 的决策方向反推
                if (f[i - 1][j] >= f[i][j - 1]) {
                    // LCS 来自上方，说明此字符来自 str1
                    res += str1[i - 1];
                    --i;
                } else {
                    // LCS 来自左方，说明此字符来自 str2
                    res += str2[j - 1];
                    --j;
                }
            }
        }

        // 处理剩余字符
        while (i > 0) {
            res += str1[i - 1];
            --i;
        }
        while (j > 0) {
            res += str2[j - 1];
            --j;
        }

        // 由于是从后向前构造，需要反转
        reverse(res.begin(), res.end());
        return res;
    }
};