我很难理解为什么多个字符串（k>2）的最长公共子序列问题是np难的。我知道长度为l1，l2的两个字符串的lcs问题可以在o（l1*l2）时间内得到解决。我的问题是为什么我们不能同时找到两个字符串的LCS，例如：
LCS（abcd，ad，abc）=LCS（LCS（abcd，ad），abc）=LCS（ad，abc）=a
该算法对k个字符串取o（k*max_length^2）。为什么这是错的？
最佳答案
lcs（x，y，z）通常不是真的例如：
LCS（bb，aaaaaaaa，bbaaaa）=bb
LCS（bb，LCS（aaaa，bb aaa））=LCS（bb，aaa）