python - 3个以上字符串的最长公共(public)子序列

Question

我试图找到 3 个或更多字符串的最长公共(public)子序列。维基百科文章对 how to do this for 2 strings 有很好的描述，但我有点不确定如何将其扩展到 3 个或更多字符串。

有很多库可用于查找 2 个字符串的 LCS，因此如果可能，我想使用其中一个。如果我有 3 个字符串 A、B 和 C，找到 A 和 B 的 LCS 作为 X，然后找到 X 和 C 的 LCS 是否有效，或者这是错误的方法吗？

我在 Python 中实现如下:

import difflib

def lcs(str1, str2):
    sm = difflib.SequenceMatcher()
    sm.set_seqs(str1, str2)
    matching_blocks = [str1[m.a:m.a+m.size] for m in sm.get_matching_blocks()]
    return "".join(matching_blocks)

print reduce(lcs, ['abacbdab', 'bdcaba', 'cbacaa'])

这会输出“ba”，但它应该是“baa”。

Answer 1

只是概括递归关系。

对于三个字符串:

dp[i, j, k] = 1 + dp[i - 1, j - 1, k - 1] if A[i] = B[j] = C[k]
              max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise

应该很容易从中推广到更多字符串。