python - 最长公共(public)序列的长度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,'','')

输入:

abccdabab 
bacdbeb 

预期输出: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 或 ystr 开头删除字符所找到的长度来找到最大的最长公共(public)子字符串长度，不是两者都.

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

然后，您可以通过查看 xtail 和 ytail(实际尾部)来尝试优化并尽早退出:

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:
        if xtail == ytail:
            # if the tails match, bail out early
            return 1 + len(xtail)
        return 1 + llcs(xtail, ytail)
    return max(llcs(xstr, ytail), llcs(xtail, ystr))