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

Question

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

7

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

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

print a.llcs(b)

>>> 3

我试图找到最长公共子序列，然后获取其长度，但我认为必须有更好的解决方案。

- Milano

1

你的样例输出是错误的；LCS 是 [2, 6, 5, 4]，因此长度是 4。 - Martijn Pieters

@MartijnPieters 不，它是正确的。LCS是[6,5,4]，再看一遍 :) 你的函数也是这样说的。 >>> 3 - Milano

1

那不是LCS。它可能是最长的连续子序列，但不是LCS。LCS不必是连续的（所有元素紧挨在一起）。你把LCS和最长公共子串问题混淆了。 - Martijn Pieters

@MartijnPieters 感谢您的解释，那么LCS是什么？它类似于两个集合的交集，但可能存在重复吗？ - Milano

两个序列都包含 [2, 6, 5, 4]，并且顺序相同。在 a 中，这些元素是连续的，但在 b 中有一个值在它们之间（1），但它是 a 和 b 的子序列。 - Martijn Pieters

请参阅Wikipedia文章；简介中也指出了常见的混淆。 - Martijn Pieters

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martijn Pieters · Accepted Answer

你可以轻松地将最长公共子序列（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