最长公共序列的长度 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

预计output:5
我get: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 的开头删除字符找到的长度来找到最大最长公共子串长度，而不是两者 .

您的代码绝不会将 X 与 Y[1:] 或 X[1:] 与 Y 配对用于 max() 调用，因此您永远不会找到 LCS对于 X 或 Y.

中的特定起始字符

然后您可以通过查看 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))

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

Length of Longest Common sequence Python recursive function

python

longest-substring