如何求指数时间内的最长公共子序列？

Question

我可以使用动态编程以正确的方式做到这一点，但我不知道如何在指数时间内做到这一点。

我正在寻找两个字符串之间最大的公共子序列。 注意：我的意思是子序列而不是子串，组成序列的符号不必是连续的。

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

Answer 2

假设您有两个长度为 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

Answer 3

字符串A和字符串B。一个递归算法，也许它很幼稚，但很简单：

看看A的第一个字母。这要么是一个共同的序列，要么不是。当考虑“not”选项时，我们修剪掉第一个字母并递归调用。当考虑“处于公共序列中”选项时，我们也会将其修剪掉，并且还会从 B 的开头一直修剪到 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 小于找到的最长子序列时提前返回）所以 远的。

Answer 4

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

Answer 5

为了实现指数时间，生成两个数组的所有子序列并将每个子序列相互比较就足够了。如果匹配两个相同的长度，请检查它们的长度是否大于当前的最大值。伪代码是：

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++;

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