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成有限责任公司：

def lcs_length(a, b): 
    table = [[0] * (len(b) + 1) for _ in xrange(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 

如果你想要的longest common substring（一不同，但相关的问题，其中序列是连续），使用：

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

这与lcs_length动态编程方法非常相似，但我们追踪到目前为止发现的最大长度（因为不再保证表中的最后一个元素是最大值）。

这将返回3：

>>> lcsubstring_length(a, b) 
3 

稀疏表变种不必跟踪所有0 S：

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