最长公共序列的长度的Python递归函数

Question

我试图用python中的递归实现这个函数，但我有一个错误。我不明白是什么错，你能帮帮我吗？在

代码：

def LongestCommonSubsequence(X,Y,tailX,tailY):
    if tailX == tailY and tailX!='' and (X=='' or Y==''):
            return len(tailX)
    elif X=='' or Y=='':
            return 0
    else:

        return max( LongestCommonSubsequence(X[1:],Y[1:],tailX+X[0],tailY+Y[0]),
                    LongestCommonSubsequence(X[1:],Y[1:],tailX+X[0],tailY),
                    LongestCommonSubsequence(X[1:],Y[1:],tailX,tailY+Y[0]),
                    LongestCommonSubsequence(X[1:],Y[1:],tailX,tailY)) 

X=raw_input() 
Y=raw_input() 
print LongestCommonSubsequence(X,Y,'','')

输入：

^{pr2}$

期望输出：5
什么我获得：4在

Answer 1

在这里，您似乎在尝试为常见的尾部字符串进行优化；如果两个字符串都以相同的尾部结尾，那么您确实可以跳过一些递归步骤。在

但实际上你并不是在构建一个尾巴，而是在构建一个开头的角色。在

下面是一个工作递归llcs，没有这个优化：

def llcs(xstr, ystr):
    if not xstr or not ystr:
        return 0
    x, xtail, y, ytail = xstr[0], xstr[1:], ystr[0], ystr[1:]
    if x == y:
        return 1 + llcs(xtail, ytail)
    return max(llcs(xstr, ytail), llcs(xtail, ystr))

它通过比较从xstr或{}开头删除字符而找到的最大最长公共子串长度，而不是两者。在

对于max()调用，您的代码不会将X与Y[1:]或{}与{}配对，因此您永远不会在X或{}中找到该特定起始字符的LCS。在

然后，您可以通过查看xtail和ytail（实际的尾部）来尝试优化，并提前退出：

^{pr2}$