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.
You can easily retool a LCS into a LLCS:
Demo:
If you wanted the longest common substring (a different, but related problem, where the subsequence is contiguous), use:
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).This returns
3
:A sparse table variant to not have to track all the
0
s: