最长公共子序列的变种：最短公共超序列
字数 2979 2025-12-07 09:15:53

最长公共子序列的变种：最短公共超序列

题目描述

给定两个字符串 s1 和 s2，你需要找到这两个字符串的最短公共超序列（Shortest Common Supersequence, SCS）的长度。
最短公共超序列是指一个最短的字符串，使得 s1 和 s2 都是这个字符串的子序列（不一定连续）。
例如：
s1 = "abac", s2 = "cab"

  • 一个可能的超序列是 "cabac"（其中 s1 可通过保留第 2、3、4、5 个字符得到，s2 可通过保留第 1、2、3 个字符得到），但它不是最短的。
  • 最短的超序列是 "cabac" 的长度是 5，但其实还有更短的 "cabac" 可以验证，实际上正确答案是 "cabac" 的长度 5。更短的是 "caba" 长度 4 无法同时是 s1 和 s2 的超序列。
    准确来说，s1 = "abac", s2 = "cab" 的最短公共超序列是 "cabac"，长度 5。
    现在，请你设计一个算法求出最短公共超序列的长度。

解题思路

我们可以从最长公共子序列（LCS）出发来思考。
假设我们已经知道了 s1 和 s2 的最长公共子序列的长度为 lcs。

  • 对于公共子序列中的每个字符，它在最终的超序列中只需要出现一次。
  • 对于非公共子序列部分的字符，它们必须都出现在超序列中。
    所以，最短公共超序列的长度是：

\[\text{len}(s1) + \text{len}(s2) - lcs \]

因为 LCS 被重复计算了一次，所以要减去一次。

例子验证：
s1 = "abac"（长度 4），s2 = "cab"（长度 3），它们的 LCS 是 "ab" 长度 2，
所以 SCS 长度 = 4 + 3 - 2 = 5，与前面一致。

因此，问题转化为：先求 LCS 的长度，然后通过公式计算 SCS 长度。
我们也可以直接通过动态规划求解 SCS 长度，不依赖 LCS 的显式求解。

动态规划解法步骤

定义状态
设 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最短公共超序列的长度。

  • i 范围：0 到 len(s1)
  • j 范围：0 到 len(s2)

初始条件

  • 如果 i = 0，那么超序列就是 s2 的前 j 个字符，所以 dp[0][j] = j。
  • 如果 j = 0，那么超序列就是 s1 的前 i 个字符，所以 dp[i][0] = i。

状态转移
考虑 s1[i-1] 和 s2[j-1]（因为索引从 0 开始，前 i 个字符的最后一个字符是 s1[i-1]）：

  1. 如果 s1[i-1] == s2[j-1]，那么这个字符在超序列中只需要出现一次，所以：

\[ dp[i][j] = dp[i-1][j-1] + 1 \]

表示在 s1 前 i-1 和 s2 前 j-1 的超序列后面加上这个字符。
2. 如果 s1[i-1] != s2[j-1]，那么当前字符不同，超序列必须包含两者之一，并继续匹配剩下的部分。这时有两种选择：

  • 将 s1[i-1] 加入超序列，然后匹配 s1 前 i-1 和 s2 前 j，即 dp[i-1][j] + 1。
  • 将 s2[j-1] 加入超序列，然后匹配 s1 前 i 和 s2 前 j-1，即 dp[i][j-1] + 1。
    我们取最小值，因为要找最短超序列：

\[ dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + 1 \]

最终结果
dp[n][m] 就是最短公共超序列的长度，其中 n = len(s1), m = len(s2)。

例子演示

s1 = "abac", s2 = "cab"
n=4, m=3
初始化：

dp[0][0] = 0  
dp[1][0] = 1, dp[2][0] = 2, dp[3][0] = 3, dp[4][0] = 4  
dp[0][1] = 1, dp[0][2] = 2, dp[0][3] = 3

计算过程（表格，dp[i][j]）：

  • i=1, j=1: s1[0]='a', s2[0]='c' 不同 → min(dp[0][1], dp[1][0])+1 = min(1,1)+1=2
  • i=1, j=2: s1[0]='a', s2[1]='a' 相同 → dp[0][1]+1 = 1+1=2
  • i=1, j=3: s1[0]='a', s2[2]='b' 不同 → min(dp[0][3], dp[1][2])+1 = min(3,2)+1=3
  • i=2, j=1: s1[1]='b', s2[0]='c' 不同 → min(dp[1][1], dp[2][0])+1 = min(2,2)+1=3
  • i=2, j=2: s1[1]='b', s2[1]='a' 不同 → min(dp[1][2], dp[2][1])+1 = min(2,3)+1=3
  • i=2, j=3: s1[1]='b', s2[2]='b' 相同 → dp[1][2]+1 = 2+1=3
  • i=3, j=1: s1[2]='a', s2[0]='c' 不同 → min(dp[2][1], dp[3][0])+1 = min(3,3)+1=4
  • i=3, j=2: s1[2]='a', s2[1]='a' 相同 → dp[2][1]+1 = 3+1=4
  • i=3, j=3: s1[2]='a', s2[2]='b' 不同 → min(dp[2][3], dp[3][2])+1 = min(3,4)+1=4
  • i=4, j=1: s1[3]='c', s2[0]='c' 相同 → dp[3][0]+1 = 3+1=4
  • i=4, j=2: s1[3]='c', s2[1]='a' 不同 → min(dp[3][2], dp[4][1])+1 = min(4,4)+1=5
  • i=4, j=3: s1[3]='c', s2[2]='b' 不同 → min(dp[3][3], dp[4][2])+1 = min(4,5)+1=5

最终 dp[4][3] = 5，与公式结果一致。

复杂度分析

  • 时间复杂度：O(n×m)，需要填满 DP 表。
  • 空间复杂度：O(n×m)，可以优化为 O(min(n,m)) 通过滚动数组，因为当前行只依赖于上一行和当前行的前一个值。

扩展：构造最短公共超序列本身

如果想构造出这个超序列，可以在 DP 填表后回溯：

  • 从 (n,m) 开始，如果 s1[i-1]==s2[j-1]，把该字符加入结果，然后移动到 (i-1,j-1)。
  • 如果不等，比较 dp[i-1][j] 和 dp[i][j-1]，选择小的方向移动，并把对应的字符加入结果。
  • 直到 i=0 或 j=0，把剩余的字符加入结果。
  • 最后反转结果字符串即可得到最短公共超序列。

通过上述步骤，我们不仅能求出长度，还能构造出具体的最短公共超序列。这就是这个线性动态规划问题的完整解法。

最长公共子序列的变种：最短公共超序列 题目描述 给定两个字符串 s1 和 s2 ，你需要找到这两个字符串的最短公共超序列（Shortest Common Supersequence, SCS）的长度。 最短公共超序列是指一个最短的字符串，使得 s1 和 s2 都是这个字符串的子序列（不一定连续）。 例如： s1 = "abac" , s2 = "cab" 一个可能的超序列是 "cabac" （其中 s1 可通过保留第 2、3、4、5 个字符得到， s2 可通过保留第 1、2、3 个字符得到），但它不是最短的。 最短的超序列是 "cabac" 的长度是 5，但其实还有更短的 "cabac" 可以验证，实际上正确答案是 "cabac" 的长度 5。更短的是 "caba" 长度 4 无法同时是 s1 和 s2 的超序列。 准确来说， s1 = "abac" , s2 = "cab" 的最短公共超序列是 "cabac" ，长度 5。 现在，请你设计一个算法求出最短公共超序列的长度。 解题思路 我们可以从最长公共子序列（LCS）出发来思考。 假设我们已经知道了 s1 和 s2 的最长公共子序列的长度为 lcs 。 对于公共子序列中的每个字符，它在最终的超序列中只需要出现一次。 对于非公共子序列部分的字符，它们必须都出现在超序列中。 所以，最短公共超序列的长度是： \[ \text{len}(s1) + \text{len}(s2) - lcs \] 因为 LCS 被重复计算了一次，所以要减去一次。 例子验证 ： s1 = "abac" （长度 4）， s2 = "cab" （长度 3），它们的 LCS 是 "ab" 长度 2， 所以 SCS 长度 = 4 + 3 - 2 = 5，与前面一致。 因此，问题转化为：先求 LCS 的长度，然后通过公式计算 SCS 长度。 我们也可以直接通过动态规划求解 SCS 长度，不依赖 LCS 的显式求解。 动态规划解法步骤 定义状态 设 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最短公共超序列的长度。 i 范围：0 到 len(s1) j 范围：0 到 len(s2) 初始条件 如果 i = 0 ，那么超序列就是 s2 的前 j 个字符，所以 dp[0][j] = j 。 如果 j = 0 ，那么超序列就是 s1 的前 i 个字符，所以 dp[i][0] = i 。 状态转移 考虑 s1[i-1] 和 s2[j-1] （因为索引从 0 开始，前 i 个字符的最后一个字符是 s1[ i-1 ]）： 如果 s1[i-1] == s2[j-1] ，那么这个字符在超序列中只需要出现一次，所以： \[ dp[ i][ j] = dp[ i-1][ j-1 ] + 1 \] 表示在 s1 前 i-1 和 s2 前 j-1 的超序列后面加上这个字符。 如果 s1[i-1] != s2[j-1] ，那么当前字符不同，超序列必须包含两者之一，并继续匹配剩下的部分。这时有两种选择： 将 s1[i-1] 加入超序列，然后匹配 s1 前 i-1 和 s2 前 j，即 dp[i-1][j] + 1 。 将 s2[j-1] 加入超序列，然后匹配 s1 前 i 和 s2 前 j-1，即 dp[i][j-1] + 1 。 我们取最小值，因为要找最短超序列： \[ dp[ i][ j] = \min(dp[ i-1][ j], dp[ i][ j-1 ]) + 1 \] 最终结果 dp[n][m] 就是最短公共超序列的长度，其中 n = len(s1) , m = len(s2) 。 例子演示 s1 = "abac" , s2 = "cab" n=4, m=3 初始化： 计算过程（表格，dp[ i][ j ]）： i=1, j=1: s1[ 0]='a', s2[ 0]='c' 不同 → min(dp[ 0][ 1], dp[ 1][ 0 ])+1 = min(1,1)+1=2 i=1, j=2: s1[ 0]='a', s2[ 1]='a' 相同 → dp[ 0][ 1 ]+1 = 1+1=2 i=1, j=3: s1[ 0]='a', s2[ 2]='b' 不同 → min(dp[ 0][ 3], dp[ 1][ 2 ])+1 = min(3,2)+1=3 i=2, j=1: s1[ 1]='b', s2[ 0]='c' 不同 → min(dp[ 1][ 1], dp[ 2][ 0 ])+1 = min(2,2)+1=3 i=2, j=2: s1[ 1]='b', s2[ 1]='a' 不同 → min(dp[ 1][ 2], dp[ 2][ 1 ])+1 = min(2,3)+1=3 i=2, j=3: s1[ 1]='b', s2[ 2]='b' 相同 → dp[ 1][ 2 ]+1 = 2+1=3 i=3, j=1: s1[ 2]='a', s2[ 0]='c' 不同 → min(dp[ 2][ 1], dp[ 3][ 0 ])+1 = min(3,3)+1=4 i=3, j=2: s1[ 2]='a', s2[ 1]='a' 相同 → dp[ 2][ 1 ]+1 = 3+1=4 i=3, j=3: s1[ 2]='a', s2[ 2]='b' 不同 → min(dp[ 2][ 3], dp[ 3][ 2 ])+1 = min(3,4)+1=4 i=4, j=1: s1[ 3]='c', s2[ 0]='c' 相同 → dp[ 3][ 0 ]+1 = 3+1=4 i=4, j=2: s1[ 3]='c', s2[ 1]='a' 不同 → min(dp[ 3][ 2], dp[ 4][ 1 ])+1 = min(4,4)+1=5 i=4, j=3: s1[ 3]='c', s2[ 2]='b' 不同 → min(dp[ 3][ 3], dp[ 4][ 2 ])+1 = min(4,5)+1=5 最终 dp[ 4][ 3 ] = 5，与公式结果一致。 复杂度分析 时间复杂度：O(n×m)，需要填满 DP 表。 空间复杂度：O(n×m)，可以优化为 O(min(n,m)) 通过滚动数组，因为当前行只依赖于上一行和当前行的前一个值。 扩展：构造最短公共超序列本身 如果想构造出这个超序列，可以在 DP 填表后回溯： 从 (n,m) 开始，如果 s1[ i-1]==s2[ j-1 ]，把该字符加入结果，然后移动到 (i-1,j-1)。 如果不等，比较 dp[ i-1][ j] 和 dp[ i][ j-1 ]，选择小的方向移动，并把对应的字符加入结果。 直到 i=0 或 j=0，把剩余的字符加入结果。 最后反转结果字符串即可得到最短公共超序列。 通过上述步骤，我们不仅能求出长度，还能构造出具体的最短公共超序列。这就是这个线性动态规划问题的完整解法。