我想找出n个字符串中最长的公共子序列。我得到了对2个字符串使用动态编程的算法，但是如果我将它扩展到N，它将消耗指数级的内存，因为我需要一个N维数组这不是一个选择。
在一般情况下（90%），几乎所有字符串都是相同的。
如果我尝试将N个序列分成N/2对，每组2个字符串，分别为每对运行2个字符串的LCS，我将拥有N/2个子序列我可以删除重复项并重复此过程，直到只有一个子序列，这是输入中所有字符串的通用子序列。
有什么东西我遗漏了吗？这看起来不像是解决n个难题的办法…
我知道使用每对字符串对LCS的每个调用都可能有多个子序列作为解决方案，但是如果我在下一个调用中只得到这些子序列中的一个子序列作为输入，那么我的最终子序列可能不是最长的，但是我有一些可能符合我需要的东西。
如果我尝试对一对使用所有可能的解，然后与来自另一对的所有可能的解组合（每个解可能也有多个解），我可能会以指数时间结束我说得对吗？
最佳答案
是的，您遗漏了正确性：不能保证一对字符串的LCS与集合整体的LCS有任何重叠举个例子：
aaabb1xyz
aaabb2xyz
cccdd1xyz
cccdd2xyz
如果按给定的顺序配对，则会得到
aaabb和cccdd的lcs，缺少集合的xyz。如果，正如你所说，字符串几乎都是相同的，那么差异对你来说也许不是问题如果不完全相同的字符串与“中值”字符串非常相似，那么您的增量解决方案就足以满足您的需要。
另一种可能性是对随机字符串对进行LCS，直到出现中间字符串；然后从公共点开始，应该有一个“足够好”的解决方案。
关于algorithm - N个序列的最长公共(public)子序列(用于不同目的)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47062351/