4

我可以使用动态编程以正确的方式做到这一点，但我无法弄清楚如何在指数时间内做到这一点。

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

4

6 回答 6

6

只需将动态编程代码中的表中的查找替换为递归调用即可。换句话说，只需实现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))
于 2012-01-25T21:24:54.650 回答
1

假设您有两个字符串a和b长度n。最长的公共子序列将是 string 中最长的子序列a，它也存在于 string 中b。

因此我们可以遍历所有可能的子序列 ina并看到它在b.

对此的高级伪代码将是：

for i=n to 0
    for all length i subsequences s of a
        if s is a subsequence of b
            return s
于 2012-01-25T21:51:49.777 回答
1

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

查看 A 的第一个字母。这将是一个共同的序列，也可能不是。在考虑“not”选项时，我们会删除第一个字母并递归调用。当考虑 'is in a common sequence' 选项时，我们也将其修剪掉，并且从 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小于迄今为止发现的最长长度时）。

于 2012-01-25T22:13:37.550 回答
0

本质上，如果您不使用动态编程范式-您将达到指数时间。这是因为，通过不存储您的部分值 - 您正在多次重新计算部分值。

于 2012-01-25T21:49:26.370 回答
0

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

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

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

于 2016-08-17T12:59:03.553 回答
-1 
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)序列。

于 2016-08-16T08:42:57.217 回答