string - 最短通用超弦算法？

Question

我试图在这里编写这个问题：

但我想找到一种算法来分解解决问题的步骤。我似乎在网上找不到任何太有用的东西，所以我来这里询问是否有人知道我可以用来引用解决此问题的算法的资源。

Answer 1

这被称为最短公共超序列问题。这个想法是，为了使超序列最短，我们希望找到尽可能多的 a 和 b 的共享位。我们可以分两步解决这个问题：

1. 找出 a 和 b 的最长公共子序列。

2. 插入 a 和 b 的剩余位，同时保留这些位的顺序。

我们可以使用动态规划解决最长公共子序列问题。

Answer 2

我同意 Terry Li 的观点：找到多个序列的 SCS 只是 NP 完全的。对于 2 个序列（例如 s 的长度为 n，t 的长度为 m），我的解决方案（不使用 LCS，但使用类似的东西）在 O(nm) 时间内完成：

1）运行全局对齐，在其中您不允许不匹配，不要惩罚插入缺失，并给匹配打正分（我对匹配做了+1，对不匹配做了-10，对插入缺失做了0，但这些可以调整） . （这是 O(nm)）

2) 迭代输出字符串 v 和 w 的全局对齐。如果 v[i] 不是间隙，则输出它。否则，输出 w[i]。（这是 O(n+m)）。