Python：列表的最长公共子序列长度

Question

在Python里有没有一个内置的函数可以返回两个列表中最长公共子序列的长度呢？

a=[1,2,6,5,4,8]
b=[2,1,6,5,4,4]

print a.llcs(b)

>>> 3

我试着找出最长公共子序列，然后再计算它的长度，但我觉得应该有更好的方法。

Answer 1

你可以很简单地把一个最长公共子序列（LCS）的问题转变为一个最长公共子序列的长度（LLCS）的问题：

def lcs_length(a, b):
    table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i, ca in enumerate(a, 1):
        for j, cb in enumerate(b, 1):
            table[i][j] = (
                table[i - 1][j - 1] + 1 if ca == cb else
                max(table[i][j - 1], table[i - 1][j]))
    return table[-1][-1]

示例：

>>> a=[1,2,6,5,4,8]
>>> b=[2,1,6,5,4,4]
>>> lcs_length(a, b)
4

如果你想找的是最长公共子串（这是一个不同但相关的问题，子串是连续的），可以使用：

def lcsubstring_length(a, b):
    table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    longest = 0
    for i, ca in enumerate(a, 1):
        for j, cb in enumerate(b, 1):
            if ca == cb:
                length = table[i][j] = table[i - 1][j - 1] + 1
                longest = max(longest, length)
    return longest

这个方法和lcs_length的动态规划方法非常相似，不过我们需要记录到目前为止找到的最大长度（因为现在不再保证表格中的最后一个元素就是最大值）。

这个方法返回3：

>>> lcsubstring_length(a, b)
3

还有一种稀疏表的变体，可以避免跟踪所有的0（如果a和b可能非常大，可以使用这个）：

def lcsubstring_length(a, b):
    table = {}
    longest = 0
    for i, ca in enumerate(a, 1):
        for j, cb in enumerate(b, 1):
            if ca == cb:
                length = table[i, j] = table.get((i - 1, j - 1), 0) + 1
                longest = max(longest, length)
    return longest