什么是查找所有子字符串出现的最快方法？

Question

这只是出于好奇。我正在浏览一篇比较各种字符串搜索算法的文章，发现它们都设计用于找到第一个匹配的子字符串。这让我想...如果我想要找到所有子字符串的出现呢？

我相信我可以创建一个循环，使用KMP或BM的变体，并将每个找到的出现转储到一个数组中，但这似乎并不是最快的方法。

分治算法难道不是更好的选择吗？

例如，假设您正在查找字符串“abc”在字符串“abbcacabbcabcacbccbabc”中的所有出现。

1. 在第一次查找时，找到第一个字符的所有出现并存储它们的位置。
2. 在每个附加通行证上，使用前一个通行证中的位置查找下一个字符的所有出现，每次迭代都减少下一个通行证的候选项。

考虑到我想出这个想法的轻松程度，我认为30年前已经有人提出了这个想法并进行了改进。

- Kenneth Cochran

---

这要视情况而定。如果你有字符串 "aaaaaa"，那么其中有多少个 "aa"？3 个？5 个？这也取决于你使用的编程语言。 - Peter

Answer 1

参见后缀数组

应用

字符串的后缀数组可用作索引，快速定位字符串中每个子串的每个出现位置。查找每个子串的每个出现位置等同于查找以该子串开头的每个后缀。由于词典序排序，这些后缀会在后缀数组中被分组，并可以通过二分搜索高效地找到。如果直接实现，则此二分搜索需要O(mlogn)时间，其中m是子串的长度。为避免重新比较，构建额外的数据结构来提供有关后缀最长公共前缀（LCP）的信息，使得搜索时间为O(m+logn)。

- Nick Dandoulakis

Answer 2

如果您只需要处理给定的字符串一次，那么后缀数组就有点过头了。它需要O(n log n)的时间来创建，因此KMP算法会更快。此外，如果您的字符串非常大，或者希望在接收字符串时实时获得结果，则后缀数组无法胜任。

可以修改KMP算法以在找到匹配项后继续进行，而不需要额外的内存，除了用于存储匹配项的内存（如果您只是打印出匹配项或在处理它们时沿途进行处理，则可能是不必要的）。首先，取维基百科实现并将“return m”语句修改为“将m添加到索引列表中”。但你还没有完成。您还需要问自己，是否允许重叠的出现？例如，如果您的子字符串是“abab”，并且您正在查找主字符串“abababab”，那么有两个还是三个出现？在我给出的示例中（“作为起点”），您可以将i重置为0以给出“两个”答案，或者在“add m”之后穿过“otherwise”情况以给出“三个”答案。

- Martin Hock

Answer 3

没有单一的“最快方法”，它取决于：

A）字符串实际上是由什么构建的（长度、字符分布等）

B）在哪种硬件上运行

C）如果您希望所有结果并行还是顺序

D）其他参数（例如，可以找到的元素是否重叠，您是要搜索一次还是多次）

E）如果您认为这个实现是特定的还是仅仅学术性的。在实现中，有很多额外的优化方法。例如，临时存储（就像您的建议中）通常非常昂贵。

例如，您提出的想法会完全破坏长字符串的任何CPU缓存。因此，在这些情况下，它将非常慢。

- Foxfire

Answer 4

无论是KMP还是BM都可以轻松地用于查找多个匹配项。我还建议使用Rabin-Karp，我认为它更容易理解，但对于多个匹配项来说并不是真正的快速算法（我想时间复杂度是O(n+k*m)，其中n是文本长度，m是模式长度，k是出现次数）。但它很容易修改以实现重叠和非重叠匹配。

也可以使用后缀树/后缀数组来完成，但它们编码难度较大，而且并不能真正提高速度。

- MAK