最短子序列时间复杂度

Question

如果我们有两个字母序列X=和Y=。我们希望找到最短的序列，这样X和Y就会成为该序列的子序列。这项工作的时间复杂性是多少？

1) O(nm)

( 2) O(n+m)

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

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

感谢任何人

Answer 1

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

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

由于没有一个LCS解是线性的，求解LCS也将主导求解这个问题的算法。LCS解决方案的复杂性取决于几个因素，例如字母表的长度。

m)。

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