3个字符串中最长的公共子序列 LCS(LCS(string ,string),string)
longest common subsequence in 3 strings in this way LCS(LCS(string ,string),string)
假设我们要查找 3 个字符串的 LCS。找到 LCS (LCS(string,x, string y), string z) 是否给出了正确的解决方案？
不，不是。
用这个反例：
x = 'baa', y = 'aab', z = 'b' 您可以看到 lcs(x, y, z) = 'b'，以及 lcs(lcs(x, y), z) = lcs('aa', 'b') = ''。
附带说明一下，虽然可以在多项式时间内找到两个字符串之间的 LCS，但在任意数量的字符串之间找到公共 LCS 的问题是 NP-hard。
假设我们要查找 3 个字符串的 LCS。找到 LCS (LCS(string,x, string y), string z) 是否给出了正确的解决方案？
不，不是。
用这个反例：
x = 'baa', y = 'aab', z = 'b' 您可以看到 lcs(x, y, z) = 'b'，以及 lcs(lcs(x, y), z) = lcs('aa', 'b') = ''。
附带说明一下，虽然可以在多项式时间内找到两个字符串之间的 LCS，但在任意数量的字符串之间找到公共 LCS 的问题是 NP-hard。