最短公共超序列（Shortest Common Supersequence, SCS）问题
字数 3029 2025-12-13 19:28:09

最短公共超序列（Shortest Common Supersequence, SCS）问题

描述
最短公共超序列（SCS）问题是一个经典的序列处理问题，旨在寻找一个最短的字符串，使得该字符串包含两个（或多个）给定序列作为其子序列。这里的“子序列”不要求连续，但必须保持原有字符的相对顺序。例如，给定字符串 X = "ABCBDAB" 和 Y = "BDCAB"，它们的一个最短公共超序列是 "ABCBDCAB"（长度为 8）。
该问题在生物信息学（如基因组装配）、版本控制（如合并文件变更）和数据压缩等领域有广泛应用。

解题过程
SCS 问题与最长公共子序列（LCS）问题密切相关，可以通过 LCS 的结果构造出 SCS。解题思路分为两步：

  1. 求出两个序列的最长公共子序列（LCS）。
  2. 基于 LCS，合并两个序列得到最短公共超序列。

第一步：求解最长公共子序列（LCS）

对于两个序列 X[1…m] 和 Y[1…n]，我们使用动态规划求解 LCS。

1.1 定义状态

定义 dp[i][j] 为 X[1…i] 和 Y[1…j] 的最长公共子序列的长度。

  • i 范围：0 到 m（i=0 表示空序列）。
  • j 范围：0 到 n（j=0 表示空序列）。

1.2 状态转移方程

  • 如果 i == 0 或 j == 0，则 dp[i][j] = 0（空序列的 LCS 长度为 0）。
  • 如果 X[i] == Y[j]，则 dp[i][j] = dp[i-1][j-1] + 1（当前字符匹配，长度加 1）。
  • 如果 X[i] != Y[j]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])（取两个子问题的较大值）。

1.3 计算示例

以 X = "ABCBDAB"（m=7）、Y = "BDCAB"（n=5）为例，构建 dp 表（部分关键值）：

  • 初始化：第 0 行和第 0 列为 0。
  • 计算过程（箭头表示依赖关系）：
    • X[1]='A', Y[1]='B' → 不匹配 → dp[1][1] = max(0,0)=0
    • X[2]='B', Y[1]='B' → 匹配 → dp[2][1] = dp[1][0]+1=1
    • … 逐步填表 …
      最终 dp[7][5] = 4，对应 LCS 长度为 4（如 "BCAB" 或 "BDAB"）。

1.4 回溯找出 LCS

从 dp[m][n] 开始，根据转移规则反向追踪：

  • 若 X[i] == Y[j]，则该字符属于 LCS，并移动到 dp[i-1][j-1]。
  • 若 X[i] != Y[j]，则向 dp[i-1][j] 和 dp[i][j-1] 中较大值方向移动（若相等，任选其一）。
    追踪得到 LCS 序列（假设为 "BCAB"）。

第二步：基于 LCS 构造最短公共超序列（SCS）

已知 LCS 后，我们可以通过“合并”两个序列来构造 SCS，规则如下：

  1. 使用双指针 i 和 j 分别遍历 X 和 Y。
  2. 使用第三个指针 k 遍历 LCS（假设为 L）。
  3. 比较当前字符：
    • 若 X[i] != L[k]，则将 X[i] 加入结果，i++。
    • 若 Y[j] != L[k]，则将 Y[j] 加入结果，j++。
    • 若 X[i] == Y[j] == L[k]，则将 L[k] 加入结果，i++, j++, k++。
  4. 当 LCS 遍历完后，将 X 和 Y 的剩余部分依次加入结果。

2.1 构造过程示例

以 X = "ABCBDAB", Y = "BDCAB", LCS = "BCAB" 为例：

  1. 初始化：i=1（A）, j=1（B）, k=1（B）。
  2. 步骤：
    • X[i]=A ≠ L[k]=B → 加入 A, i=2。
    • X[i]=B = L[k]=B 且 Y[j]=B = L[k] → 加入 B, i=3, j=2, k=2。
    • X[i]=C ≠ L[k]=C（等? 稍等：LCS "BCAB" 第二个字符是 C） → 这里需核对：
      实际 LCS "BCAB"：索引 1:B, 2:C, 3:A, 4:B。
      此时 X[i]=C（X[3]）, Y[j]=D（Y[2]）, L[k]=C（L[2]）。
      • Y[j]=D ≠ L[k]=C → 加入 D, j=3。
      • X[i]=C = L[k]=C → 加入 C, i=4, k=3（Y[j] 未动？注意顺序）。
        实际执行时需交替处理。为清晰，列出合并表：

合并过程（逐字符）：

  • 结果字符串 S 初始为空。
  • i=1(A), j=1(B), k=1(B): A≠B → S="A", i=2。
  • i=2(B), j=1(B), k=1(B): 三者相等 → S="AB", i=3, j=2, k=2。
  • i=3(C), j=2(D), k=2(C): Y[j]=D ≠ C → S="ABD", j=3。
  • i=3(C), j=3(C), k=2(C): 三者相等 → S="ABDC", i=4, j=4, k=3。
  • i=4(B), j=4(A), k=3(A): X[i]=B ≠ A → S="ABDCB", i=5。
  • i=5(D), j=4(A), k=3(A): X[i]=D ≠ A → S="ABDCBD", i=6。
  • i=6(A), j=4(A), k=3(A): 相等 → S="ABDCBDA", i=7, j=5, k=4。
  • i=7(B), j=5(B), k=4(B): 相等 → S="ABDCBDAB", i=8, j=6, k=5（结束）。

得到 SCS: "ABDCBDAB"（长度为 8）。
注：SCS 不唯一，例如 "ABCBDCAB" 也是有效解（长度 8）。

第三步：直接动态规划求 SCS 长度（可选）

若不通过 LCS，可直接定义 dp[i][j] 为 X[1…i] 和 Y[1…j] 的最短公共超序列长度。状态转移：

  • 若 X[i] == Y[j]：dp[i][j] = dp[i-1][j-1] + 1。
  • 若 X[i] != Y[j]：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1。
    初始化：dp[0][j] = j, dp[i][0] = i。
    最终 dp[m][n] 即为最短长度，回溯可构造序列。

总结

SCS 问题的核心是找到两个序列的公共结构（LCS），然后通过填充非公共部分得到最短超序列。其时间复杂度为 O(mn)，空间复杂度可通过滚动数组优化至 O(min(m,n))。若需要处理多个序列，问题变为 NP-hard，通常采用近似算法或启发式方法求解。

最短公共超序列（Shortest Common Supersequence, SCS）问题 描述 最短公共超序列（SCS）问题是一个经典的序列处理问题，旨在寻找一个最短的字符串，使得该字符串包含两个（或多个）给定序列作为其子序列。这里的“子序列”不要求连续，但必须保持原有字符的相对顺序。例如，给定字符串 X = "ABCBDAB" 和 Y = "BDCAB" ，它们的一个最短公共超序列是 "ABCBDCAB" （长度为 8）。 该问题在生物信息学（如基因组装配）、版本控制（如合并文件变更）和数据压缩等领域有广泛应用。 解题过程 SCS 问题与最长公共子序列（LCS）问题密切相关，可以通过 LCS 的结果构造出 SCS。解题思路分为两步： 求出两个序列的最长公共子序列（LCS）。 基于 LCS，合并两个序列得到最短公共超序列。 第一步：求解最长公共子序列（LCS） 对于两个序列 X[1…m] 和 Y[1…n] ，我们使用动态规划求解 LCS。 1.1 定义状态 定义 dp[i][j] 为 X[1…i] 和 Y[1…j] 的最长公共子序列的长度。 i 范围： 0 到 m （ i=0 表示空序列）。 j 范围： 0 到 n （ j=0 表示空序列）。 1.2 状态转移方程 如果 i == 0 或 j == 0 ，则 dp[i][j] = 0 （空序列的 LCS 长度为 0）。 如果 X[i] == Y[j] ，则 dp[i][j] = dp[i-1][j-1] + 1 （当前字符匹配，长度加 1）。 如果 X[i] != Y[j] ，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) （取两个子问题的较大值）。 1.3 计算示例 以 X = "ABCBDAB" （m=7）、 Y = "BDCAB" （n=5）为例，构建 dp 表（部分关键值）： 初始化：第 0 行和第 0 列为 0。 计算过程（箭头表示依赖关系）： X[1]='A' , Y[1]='B' → 不匹配 → dp[1][1] = max(0,0)=0 X[2]='B' , Y[1]='B' → 匹配 → dp[2][1] = dp[1][0]+1=1 … 逐步填表 … 最终 dp[7][5] = 4 ，对应 LCS 长度为 4（如 "BCAB" 或 "BDAB" ）。 1.4 回溯找出 LCS 从 dp[m][n] 开始，根据转移规则反向追踪： 若 X[i] == Y[j] ，则该字符属于 LCS，并移动到 dp[i-1][j-1] 。 若 X[i] != Y[j] ，则向 dp[i-1][j] 和 dp[i][j-1] 中较大值方向移动（若相等，任选其一）。 追踪得到 LCS 序列（假设为 "BCAB" ）。 第二步：基于 LCS 构造最短公共超序列（SCS） 已知 LCS 后，我们可以通过“合并”两个序列来构造 SCS，规则如下： 使用双指针 i 和 j 分别遍历 X 和 Y 。 使用第三个指针 k 遍历 LCS（假设为 L ）。 比较当前字符： 若 X[i] != L[k] ，则将 X[i] 加入结果， i++ 。 若 Y[j] != L[k] ，则将 Y[j] 加入结果， j++ 。 若 X[i] == Y[j] == L[k] ，则将 L[k] 加入结果， i++ , j++ , k++ 。 当 LCS 遍历完后，将 X 和 Y 的剩余部分依次加入结果。 2.1 构造过程示例 以 X = "ABCBDAB" , Y = "BDCAB" , LCS = "BCAB" 为例： 初始化： i=1 （ A ）, j=1 （ B ）, k=1 （ B ）。 步骤： X[i]=A ≠ L[k]=B → 加入 A , i=2 。 X[i]=B = L[k]=B 且 Y[j]=B = L[k] → 加入 B , i=3 , j=2 , k=2 。 X[i]=C ≠ L[k]=C （等? 稍等：LCS "BCAB" 第二个字符是 C ） → 这里需核对： 实际 LCS "BCAB" ：索引 1:B, 2:C, 3:A, 4:B。 此时 X[i]=C （ X[3] ）, Y[j]=D （ Y[2] ）, L[k]=C （ L[2] ）。 Y[j]=D ≠ L[k]=C → 加入 D , j=3 。 X[i]=C = L[k]=C → 加入 C , i=4 , k=3 （ Y[j] 未动？注意顺序）。 实际执行时需交替处理。为清晰，列出合并表： 合并过程 （逐字符）： 结果字符串 S 初始为空。 i=1 (A), j=1 (B), k=1 (B): A≠B → S="A" , i=2 。 i=2 (B), j=1 (B), k=1 (B): 三者相等 → S="AB" , i=3 , j=2 , k=2 。 i=3 (C), j=2 (D), k=2 (C): Y[ j]=D ≠ C → S="ABD" , j=3 。 i=3 (C), j=3 (C), k=2 (C): 三者相等 → S="ABDC" , i=4 , j=4 , k=3 。 i=4 (B), j=4 (A), k=3 (A): X[ i]=B ≠ A → S="ABDCB" , i=5 。 i=5 (D), j=4 (A), k=3 (A): X[ i]=D ≠ A → S="ABDCBD" , i=6 。 i=6 (A), j=4 (A), k=3 (A): 相等 → S="ABDCBDA" , i=7 , j=5 , k=4 。 i=7 (B), j=5 (B), k=4 (B): 相等 → S="ABDCBDAB" , i=8 , j=6 , k=5 （结束）。 得到 SCS: "ABDCBDAB" （长度为 8）。 注：SCS 不唯一，例如 "ABCBDCAB" 也是有效解（长度 8） 。 第三步：直接动态规划求 SCS 长度（可选） 若不通过 LCS，可直接定义 dp[i][j] 为 X[1…i] 和 Y[1…j] 的最短公共超序列长度。状态转移： 若 X[i] == Y[j] ： dp[i][j] = dp[i-1][j-1] + 1 。 若 X[i] != Y[j] ： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1 。 初始化： dp[0][j] = j , dp[i][0] = i 。 最终 dp[m][n] 即为最短长度，回溯可构造序列。 总结 SCS 问题的核心是找到两个序列的公共结构（LCS），然后通过填充非公共部分得到最短超序列。其时间复杂度为 O(mn)，空间复杂度可通过滚动数组优化至 O(min(m,n))。若需要处理多个序列，问题变为 NP-hard，通常采用近似算法或启发式方法求解。