问如何从同一位置找到所有可能的最长公共子序列

EN

我建议你在尝试使用任何听起来像你想做的事情的算法之前，先把这个问题转化成一个众所周知的计算问题。

这是我的建议:把这个问题转化成一个图问题。为字符串中的每个位置创建一组节点(集合中所有字符串中该位置的每个唯一字母对应一个节点...因此，如果所有700个字符串在相同位置不同，则为700个节点)。一旦您为字符串中的每个位置创建了所有节点，您将遍历您的字符串集合，查看两个位置共享3个以上相等连接的频率。在您的示例中，我们首先查看位置1和2，并看到三个字符串在位置1中包含"a“，在位置2中包含"b”，因此我们在图的第一组节点中的节点"a“和第二组节点中的"b”之间添加了一个有向边(对于所有位置对和这两个位置中的所有字母组合继续执行此操作)。您可以对每个职位组合执行此操作，直到添加了所有必要的链接。

一旦您有了最终的图，就必须寻找最长的路径；我建议您查看维基百科上的文章：Longest Path。在我们的例子中，我们将有一个有向无环图，你可以在线性时间内解决它！预处理应该是字符串位置的二次方，因为我假设你的字母表是固定大小的。

附言:你给我发了一封关于我正在研究的双簇算法的电子邮件；它还没有发表，但将在今年的某个时候发布(祈祷吧)。不过，还是要感谢您的关注:)

您可以尝试使用散列。

每个字符串最多包含25个字符。这意味着它有2^25个子序列。取每个字符串，计算所有2^25个哈希值。然后连接所有字符串的所有散列，并计算其中哪些至少包含3次。为了获得这些子序列的长度，您不仅需要存储散列，还需要存储subsequence_pointer确定散列的子序列的<hash, subsequence_pointer>对(最简单的方法是枚举所有字符串的所有散列并存储散列号)。

根据算法，在最坏的情况下(700个字符串，每个字符串25个字符)，程序将运行几分钟。