为什么多个字符串的最长公共子序列是np困难的

Question

我很难理解为什么多个字符串(k> 2)的最长公共子序列问题是NP-Hard。我知道LCS问题对于两个长度为l1 l2的字符串可以在O(l1*l2)时间内解决。我的问题是为什么我们不能一次找到两个字符串的LCS，例如:

LCS (abcd,广告,abc) = LCS (LCS (abcd,广告),abc) = LCS(广告,abc) =

对于k个字符串，该算法需要O(k*Max_length^2)。为什么这是错误的?

Answer 1

LCS(x, y, z) = LCS(x, LCS(y, z))一般不成立。例如:

LCS(bb, aaabb, bbaaa) = bb

LCS (bb, LCS (aaabb bbaaa)) = LCS (bb, aaa)≠bb