python中是否有一个内置函数可以返回两个列表的最长公共子序列的长度?
Is there a built-in function in python which returns a length of longest common subsequence of two lists?
a=[1,2,6,5,4,8] b=[2,1,6,5,4,4] print a.llcs(b) >>> 3我试图找到最长的公共子序列，然后得到它的长度，但是我认为必须有一个更好的解决方案.
I tried to find longest common subsequence and then get length of it but I think there must be a better solution.
推荐答案您可以轻松地将LCS重新构建为LLCS:
You can easily retool a LCS into a LLCS:
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如果您需要最长的常见 substring (a 不同，但相关的问题(子序列是连续的)，请使用:
If you wanted the longest common substring (a different, but related problem, where the subsequence is contiguous), use:
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动态编程方法非常相似，但是我们跟踪到目前为止找到的最大长度(因为不再保证表中的最后一个元素为最大).
This is very similar to the lcs_length dynamic programming approach, but we track the maximum length found so far (since it is no longer guaranteed the last element in the table is the maximum).
这将返回3:
>>> lcsubstring_length(a, b) 3一个稀疏表变体，不必跟踪所有0:
A sparse table variant to not have to track all the 0s:
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