最短子序列时间复杂度

Question

3

如果我们有两个字母序列X和Y，我们想要找到最短的序列，使得X和Y成为该序列的子序列。这项工作的时间复杂度是多少？

1）O(nm)

2）O(n+m)

3）O((n+m)log(n+m))

我的解决方案：我找到了一种动态规划的方法，并使用了O(nm)的顺序。有更好的解决方案吗？

谢谢任何人

- user4554402

1

它们必须成为子序列还是子串？您的文本暗示了子序列，而您的标签暗示了子串。 - IVlad

如果你有 GHIJK 和 KLMNOP，那么答案就是 GHIJKLMNOP？ - NathanOliver

亲爱的@IVlad，子序列... - user4554402

abcde和bd的预期输出是abcde，对吗？ - IVlad

1

http://en.wikipedia.org/wiki/Shortest_common_supersequence - Abhishek Bansal

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergey Kalinichenko · Accepted Answer

您可以将此问题简化为查找最长公共子序列（LCS）。

给定两个序列及其最长公共子序列，您可以使用类似于合并的贪心算法在线性时间内构造最短超序列，该算法从X或Y中添加字母到结果中，如果它们不在公共子序列中且前进到下一个字母。很容易证明该算法产生了最短超序列，否则它就与我们使用最长公共子序列的断言相矛盾。

由于没有LCS解决方案是线性的，因此解决LCS将支配寻找此问题答案的算法。 LCS解决方案的复杂度取决于多个因素，例如字母表的长度。通用LCS的解决方案为O(n*m)。

固定字母表上的LCS解决方案为O((n+m+c)*long(n+m))，其中c是公共子序列的长度。