3个以上字符串的最长公共子序列

  • Z时代
  • 2024-01-10
  • 分类：问答

我试图找到3个或更多字符串的最长公共子序列。Wikipedia文章对如何对2个字符串执行此操作进行了很好的描述，但是我不确定如何将其扩展到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”。

回答：

只需概括一下递归关系即可。

对于三个字符串：

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

应该很容易由此概括为更多的字符串。

以上是 3个以上字符串的最长公共子序列 的全部内容， 来源链接： utcz.com/qa/414260.html

回到顶部