<p>我试图找到3个或更多字符串的最长公共子序列。Wikipedia文章对<a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Solution_for_two_sequences" rel="noreferrer">how to do this for 2 strings</a>有很好的描述,但我有点不确定如何将其扩展到3个或更多字符串。</p>
<p>有很多库可以找到两个字符串的LCS,所以如果可能的话,我想使用其中的一个。如果我有3个字符串A,B和C,那么找到A和B的LCS作为X,然后找到X和C的LCS是有效的,还是这样做是错误的?</p>
<p>我用Python实现了它,如下所示:</p>
<pre><code>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'])
</code></pre>
<p>这输出“ba”,但它应该是“baa”。</p>