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