两个字符串序列中的最长公共子串

Question

刚刚学习了最长公共子串算法，对问题的一个特定变体产生了好奇。它的描述如下：

给定两个非空字符串序列X = (x1, x2, x3,....,x(n))和Y = (y1, y2, y3,..., y(m))，其中x(i)和y(i)是字符的字符串，找到X中在所有Y字符串中都是子串的最长字符串。

我有一个名为substring(x，y) 的函数，它返回布尔值，表示x是否是y的子串。显然，我必须将Y中的所有字符串连接起来形成一个大字符串B。我想到了以下方法:

- Naive: 从连接X中的所有字符串开始，形成一个字符串A(n)。应用substring(A(n)，B) - 这包括向后迭代字符串A(n)。如果为真，则算法在此处结束并返回A(n)或包含在所述子字符串中的其任何部分。否则，继续应用（A(n-1)，B）等。如果在X中不存在这样的字符串，则返回空字符串。

显然，这种方法取决于实现而需要相当长的运行时间。假设我使用迭代方法，在每次迭代中，我都必须反向遍历该级/索引中的字符串，随后应用substring()。它将至少需要两个循环，并且最坏情况下需要O(size(B)*maxlength(x1，x2，...))的时间，或者更多取决于substring()（如果我错了，请纠正我）。

我想到了一个基于后缀树/数组的第二个方法。

- Generalized Suffix Tree: 使用Ukkonen算法在O(maxlength(y1，y2，...))内构建Y序列的GST。我的后缀树知识不足。我相信后缀树方法会大大减少查找子字符串的运行时间（以空间为代价），但我不知道如何实现该操作。

如果有更好的方法，我很乐意知道。

编辑：如果我使用的不是GST，而是某些标准数据结构，例如堆栈、队列、集合、堆、优先级队列等，会怎样呢？自然地，序列X必须按大小排序，最大的字符串排在前面。如果我将它存储在一个字符串数组中，那么我将必须使用像归并排序/快速排序这样的排序算法。目标是尽可能高效地运行时间。

我能不能将X存储在一个自动排序其元素的结构中？例如最大堆？

在这种情况下，似乎后缀树是以这种方式查找子串的最佳方法。还有其他数据结构可以使用吗？

- PritishC

---

你想要一个字符串，它是Y中所有字符串的子串。但B是所有字符串的并集（而不是交集）。因此，你将会找到至少是Y中一个字符串的子串的字符串。我有什么遗漏吗？ - Abhishek Bansal

m个字符串连接后的子串不一定是这m个字符串中的一个子串。因此，以下陈述是错误的：“显然，我必须将Y中的所有字符串连接起来形成一个大字符串，称为B。” - Kris Vandermotten

Y 是一个字符串序列。我是不是应该寻找所有字符串的并集/串联呢？当我读到“Y 中的所有字符串”时，这就是我所思考的。我可能弄错了。你能举个例子来解释一下吗？ - PritishC

Answer 1

首先，将数组X按照字符串长度从长到短排序。这样，X中第一个在所有Y字符串中都是子字符串的字符串就是答案。

多处理器算法是快速解决每个X字符串与所有Y字符串匹配问题的最佳方法。

- Vishkey

---

我喜欢多处理器的方法 - 肯定会提供一些动力。然而，我正在寻找更加数据结构导向的方法。 - PritishC

我不知道你想用什么语言，但是在C语言中有mpich2库，在R语言中有foreach包。 - Vishkey

Answer 2

这是我关于解决您问题的想法；我不确定所有东西，所以如果您认为它值得努力，欢迎评论改进。

首先计算Y中所有字符串的公共子串。先取两个字符串，并构建所有公共子串的树。然后，对于Y中的每个其他字符串，从映射中删除在该字符串中未出现的每个子串。复杂度与Y中字符串的数量成线性关系，但我无法确定树中可能有多少元素，因此无法估计最终复杂度。

然后找到X中是树中某个字符串的子串的最长字符串。

还有一些改进需要进行，以尽可能地保持树的小型化，例如仅保留不是其他子串的子串。

- Bentoy13

---

这种方法需要一定的时间，因为我们需要逐个处理字符串对。 - PritishC

@TheRedBlackTree 您每次只取前两个字符串；然后您每次只取一个字符串，并从树中删除不在该字符串中的所有子字符串。我认为整个过程可以通过有意设计的数据结构加速，我在这里只是提供了我的想法。 - Bentoy13

Answer 3

记 |Y| 为集合 Y 中字符串的数量，len(Y) 为它们的总长度：

1. 将 Y 中的字符串处理成 广义后缀树（例如使用 Ukkonen 算法）。假设字母表大小固定，则时间复杂度为 O(len(Y))。

2. 根据每个节点所代表的字符串是否属于 Y 中所有字符串，在后缀树中标记。时间复杂度为 O(|Y| len(Y))。

3. 对于 X 中的每个字符串，在后缀树中查找并检查该节点是否被标记为属于 Y 中所有字符串。输出最长的已标记字符串。时间复杂度为 O(len(X))。

总时间复杂度：O(|Y| len(Y)) + O(len(X))。

- Gareth Rees

---

这似乎是一个非常可行的方法。我想知道是否有可能降低复杂度，但如果我要使用后缀树，我想这是最好的处理方式。 - PritishC