最短公共超串算法？

Question

我正在尝试编写这个问题： 但我想找到一个算法来分解解决问题的步骤。我似乎无法在网上找到任何有用的东西，所以我来这里问问是否有人知道可以用来参考解决此问题的算法资源。

- user2836553

---

在这个例子中，c 的子序列是什么？ - Abhishek Bansal

@AbhishekBansal - a 是 c 的子序列，因为 c 包含了 a 中元素的顺序。这些元素不必是连续的，只需按照相同的顺序排列即可。 - Ted Hopp

编辑：这是最短公共超序列问题，而不是最短公共超字符串。最短公共超字符串涉及查找两个字符串之间的最大重叠部分，然后合并它们。 - gowrath

Answer 1

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

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

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

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

- Terry Li

---

所需的仅是最短公共超序列的长度。我想知道计算长度是否需要像找到实际的最短公共超序列一样多的工作量（这是一个NP完全问题--请参见_Theor. Comp. Sci._，16（1981），187-198）。如果是这样，那么OP寻找“高效算法”的挑战就是不可能完成的任务。 - Ted Hopp

@TedHopp 不，找到两个序列的SCS并不是NP难题。只有在找到任意数量序列的SCS时才是NP难题 :) - Terry Li

我也在尝试解决同样的问题，您能否更详细地解释一下如何“插入剩余位”？谢谢！@TerryLi - Yoar

它仍然是NP难问题，只是2！和3！不是非常有趣的数字。 - Jason

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)）。

- Niema Moshiri