寻找N个字符串的公共子串的算法

Question

我熟悉用于2个字符串的LCS算法。现在想要找到在2个或者N个字符串中的公共子串，每一对字符串中可能有多个公共子串，在这些字符串的子集中也可能有不同的公共子串。

字符串：(ABCDEFGHIJKL) (DEF) (ABCDEF) (BIJKL) (FGH)

公共子串：

1/2 (DEF)
1/3 (ABCDEF)
1/4 (IJKL)
1/5 (FGH)
2/3 (DEF)

最长公共字符串：

1/3 (ABCDEF)

最常见的字符串：

1/2/3 (DEF)

- Dwight Kelly

---

这是一个需要特定性能算法的ACM竞赛问题吗？ - Roman

'F'子字符串不是最常见的吗？因为它出现在四个字符串中。 - interjay

告诉我们为什么你需要这个的确是个好主意，这样我们就可以理解在哪些方面我们可以进行妥协，在哪些方面不能。 - amit kumar

Roman - 我不是学生，这也不是为了比赛 :-). 该应用程序旨在查找PDF内容流中的公共元素。 interjay - 我正在忽略单个字符子字符串。 - Dwight Kelly

Answer 1

这种操作在DNA序列分析中经常使用，有多种算法可供选择。一个合理的集合可以在这里找到：这里。

还有一种蛮力方法，即制作每个子字符串的表（如果您只对较短的字符串感兴趣）：在每个级别上形成一个N元树（字母为N=26，ASCII为256），并存储每个节点的计数直方图。如果修剪掉很少使用的节点（以使内存要求合理），则最终算法可以在输入长度为N的情况下，在类似于N*M^2*log(M)的时间内找到长度最长为M的所有子序列。如果您将此拆分为K个单独的字符串，则可以构建树结构，并在通过树的单次遍历中读取答案。

- Rex Kerr

---

我来翻译这段话，意思是：基本上我就是为了说这个而来的，因为在计算生物学中经常使用这个术语。然而，“子串/子序列”的定义通常是模糊的（对于非算法专家并非故意如此），我认为在这种情况下，他的问题要求它们是连续的。 - Larry

Answer 2

除非您的字符串非常大，使内存成为问题，否则后缀树是最好的选择。对于良好的实现，每个字符在字符串中的内存使用量预计为10〜30字节。还有一些开源的实现，可以让您的工作更加轻松。

还有其他更简洁的算法，但它们更难实现（查找“压缩后缀树”）。

- luispedro