algorithm - N序列的最长公共(public)子序列(不同用途)

Question

我想找到 N 个字符串的最长公共(public)子序列。我得到了对 2 个字符串使用动态编程的算法，但是如果我将它扩展到 N，它将消耗指数数量的内存，因为我需要一个 N 维数组。这不是一个选项。

在一般情况下 (90%)，几乎所有字符串都是相同的。

如果我尝试将我的 N 个序列分解为 N/2 对，每对 2 个字符串，对每对分别运行 2 个字符串的 LCS，我将得到 N/2 个子序列。我可以删除重复项并重复此过程，直到我只有一个子序列，它对输入中的所有字符串都是通用的。

有什么我想念的吗？它看起来不像是 N 难问题的解决方案...

我知道每次使用每对字符串调用 LCS 可能有多个子序列作为解决方案，但如果我只得到这些子序列中的一个作为下一次调用的输入，也许我的最终子序列-sequence 不是最长的，但我有一些可能适合我的需要。

如果我尝试对一对使用所有可能的解决方案，然后与另一对的所有可能解决方案组合(每个对可能也有多个)，我可能会以指数时间结束。我说得对吗？

Answer 1

是的，您错过了正确性:无法保证一对字符串的 LCS 与整个字符串的 LCS 有任何重叠。考虑这个例子:

aaabb1xyz
aaabb2xyz
cccdd1xyz
cccdd2xyz

如果您按照给定的顺序将它们配对，您将获得 aaabb 和 cccdd 的 LCS，缺少该集合的 xyz。

如果像您所说的那样，字符串几乎完全相同，那么差异对您来说可能不是问题。如果不相同的字符串与“中值”字符串非常相似，那么您的增量解决方案就可以很好地满足您的目的。

另一种可能性是对随机字符串对进行 LCS，直到出现中值字符串；然后你从那个共同点开始，你应该有一个“足够好”的解决方案。