N序列的最长公共子序列（不同用途）
Longest Common Sub-sequence of N sequences (for diff purposes)
我想找到N个字符串的最长公共子序列。我得到了对 2 个字符串使用动态编程的算法，但是如果我将它扩展到 N，它将消耗指数数量的内存，因为我需要一个 N 维数组。这不是一个选项。
在一般情况下 (90%)，几乎所有字符串都是相同的。
如果我尝试在 N/2 对中打破我的 N 序列，每对 2 个字符串，运行 每对分别包含 2 个字符串的 LCS，我将有 N/2 子-序列。我可以删除重复项并重复此过程，直到我只有一个子序列，这对输入中的所有字符串都是通用的。
有什么我想念的吗？它看起来不像是 N 难问题的解决方案...
我知道每次使用每对字符串调用 LCS 可能有多个子序列作为解决方案，但如果我只得到这些子序列中的一个作为下一次调用的输入，也许我的最终的子序列不是最长的，但我有一些可能适合我的需要。
如果我尝试对一对使用所有可能的解决方案，然后与另一对的所有可能解决方案组合（每对可能有多个），我可能会以指数时间结束。我说得对吗？
是的，您没有说对：不能保证一对字符串的 LCS 与整个字符串的 LCS 有任何重叠。考虑这个例子：
aaabb1xyz
aaabb2xyz
cccdd1xyz
cccdd2xyz
如果按照给定的顺序将它们配对，您将获得 aaabb 和 cccdd 的 LCS，但缺少 xyz 组。
如果像您所说的那样，字符串几乎完全相同，那么差异对您来说可能不是问题。如果不相同的字符串与 "median" 字符串非常相似，那么您的增量解决方案就可以很好地满足您的目的。
另一种可能性是对随机字符串对进行 LCS，直到出现中值字符串；然后你从那个共同点开始，你应该有一个"good enough"解决方案。
我想找到N个字符串的最长公共子序列。我得到了对 2 个字符串使用动态编程的算法，但是如果我将它扩展到 N，它将消耗指数数量的内存，因为我需要一个 N 维数组。这不是一个选项。
在一般情况下 (90%)，几乎所有字符串都是相同的。
如果我尝试在 N/2 对中打破我的 N 序列，每对 2 个字符串，运行 每对分别包含 2 个字符串的 LCS，我将有 N/2 子-序列。我可以删除重复项并重复此过程，直到我只有一个子序列，这对输入中的所有字符串都是通用的。
有什么我想念的吗？它看起来不像是 N 难问题的解决方案...
我知道每次使用每对字符串调用 LCS 可能有多个子序列作为解决方案，但如果我只得到这些子序列中的一个作为下一次调用的输入，也许我的最终的子序列不是最长的，但我有一些可能适合我的需要。
如果我尝试对一对使用所有可能的解决方案，然后与另一对的所有可能解决方案组合（每对可能有多个），我可能会以指数时间结束。我说得对吗？
是的，您没有说对：不能保证一对字符串的 LCS 与整个字符串的 LCS 有任何重叠。考虑这个例子：
aaabb1xyz
aaabb2xyz
cccdd1xyz
cccdd2xyz
如果按照给定的顺序将它们配对，您将获得 aaabb 和 cccdd 的 LCS，但缺少 xyz 组。
如果像您所说的那样，字符串几乎完全相同，那么差异对您来说可能不是问题。如果不相同的字符串与 "median" 字符串非常相似，那么您的增量解决方案就可以很好地满足您的目的。
另一种可能性是对随机字符串对进行 LCS，直到出现中值字符串；然后你从那个共同点开始，你应该有一个"good enough"解决方案。