如何在指数时间内找到最长公共子序列？

Question

我可以使用动态规划的正确方式来解决这个问题，但我无法想出如何在指数时间内完成。

我想找到两个字符串之间的最长公共子序列。 注意：我指的是子序列而不是子字符串，即组成序列的符号不需要是连续的。

- Declan McKenna

---

一种朴素的指数算法是注意到长度为n的字符串有O(2n)个不同的子序列，因此我们可以取较短的字符串，并贪心地测试它的每个子序列是否存在于另一个字符串中。请参考：http://www.algorithmist.com/index.php/Longest_Common_Subsequence，希望这对您有所帮助。 - ChristopheD

为什么在动态规划方法可行时，你还想要指数级运行时间呢？ - Adrian

这是一个我必须准备好的潜在考试问题。 - Declan McKenna

Answer 1

只需将动态规划代码中的查找表替换为递归调用即可。换句话说，只需实现最长公共子序列问题的递归公式：LCS。

编辑

伪代码（类似Python）：

def lcs(s1, s2):
 if len(s1)==0 or len(s2)==0: return 0
 if s1[0] == s2[0]: return 1 + lcs(s1[1:], s2[1:])
 return max(lcs(s1, s2[1:]), lcs(s1[1:], s2))

- Savino Sguera

---

这在伪代码中应该怎么写？我不明白那是什么意思。 - Declan McKenna

@Deco添加了伪代码 :) 请注意，它返回LCS（s1，s2）的长度，您可以轻松地修补它以跟踪索引（即，当s1 [0] == s2 [0]时）。 - Savino Sguera

Answer 2

字符串A和字符串B。一个递归算法，也许有点天真，但它很简单：

查看A的第一个字母。这要么在一个公共序列中，要么不在。考虑“不在”的选项时，我们会去掉第一个字母并进行递归调用。考虑“在公共序列中”的选项时，我们也会去掉它，并从B的开头开始削减，直到包括B中相同的字母。一些伪代码：

def common_subsequences(A,B, len_subsequence_so_far = 0):
    if len(A) == 0 or len(B) == 0:
        return
    first_of_A = A[0] // the first letter in A.
    A1 = A[1:] // A, but with the first letter removed
    common_subsequences(A1,B,len_subsequence_so_far) // the first recursive call
    if(the_first_letter_of_A_is_also_in_B):
        Bn = ... delete from the start of B up to, and including,
             ... the first letter which equals first_of_A
        common_subsequences(A1,Bn, 1+len_subsequence_so_far )

你可以先从这里开始，然后通过记住目前为止找到的最长子序列来进行优化，当当前函数无法超过该最长长度时，可以提前返回（即当min(len(A), len(B))+len_subsequence_so_far小于目前为止找到的最长长度）。

- Aaron McDaid

Answer 3

假设你有两个长度为n的字符串：a和b。最长公共子序列将是字符串a中同时存在于字符串b中的最长子序列。

因此，我们可以遍历所有在字符串a中可能出现的子序列，并查看其是否在字符串b中。

这个算法的高层伪代码如下：

for i=n to 0
    for all length i subsequences s of a
        if s is a subsequence of b
            return s

- tskuzzy

---

@NiklasB，你能举一个反例来说明你的观点吗？ - tskuzzy

我觉得我在这里犯了一个错误。我想撤回我的踩，但它被锁定了 :/ 抱歉。 - Niklas B.

Answer 4

要实现指数级时间，只需生成两个数组的所有子序列，并将每个子序列彼此比较。如果匹配到两个完全相同的子序列，则检查它们的长度是否大于当前最大值。伪代码如下：

Generate all subsequences of `array1` and `array2`.
for each subsequence of `array1` as s1
    for each subsequece of `array2` as s2
        if s1 == s2 //check char by char
            if len(s1) > currentMax
                currentMax = len(s1)
for i = 0; i < 2^2; i++;

这绝对不是最优解。它甚至没有尝试过。然而，问题是关于非常低效的算法，所以我提供了一个。

- xenteros

Answer 5

本质上，如果您不使用动态规划范例，则会达到指数时间。这是因为，通过不存储部分值，您会多次重新计算部分值。

- Hari

Answer 6

int lcs(char[] x, int i, char[] y, int j) {
    if (i == 0 || j == 0) return 0;
    if (x[i - 1] == y[j - 1]) return lcs(x, i - 1, y, j - 1) + 1;
    return Math.max(lcs(x, i, y, j - 1), lcs(x, i - 1, y, j));
}

print(lcs(x, x.length, y, y.length);

以下是部分递归树：

                       lcs("ABCD", "AFDX")
                      /                   \
     lcs("ABC", "AFDX")                   lcs("ABCD", "AFD")
       /            \                      /               \
lcs("AB", "AFDX") lcs("AXY", "AFD")    lcs("ABC", "AFD") lcs("ABCD", "AF") 

最坏情况是LCS的长度为0，这意味着没有共同的子序列。在这种情况下，所有可能的子序列都会被检查，而且有O(2^n)个子序列。

- Selim Ekizoglu

---

嗨Selim，你能详细解释一下你的答案吗？它需要一些关于它如何工作的解释，特别是性能是否符合问题标题中“指数时间”的要求。 - Vince Bowdren