algorithm - O(N) 中字符串中子字符串的出现次数

Question

我想知道如何在线性时间内计算大海捞针中每根针的出现次数。我以为我会使用 Aho-Corasick 算法，但我不希望时间复杂度取决于针的出现次数。

Answer 1

如果您只需要出现的总数（并且您不关心位置本身），您可以有效地使用 Aho-Corasick。假设我们当前在 node 中v。有多少子串在当前位置结束。我声称这正是v后缀链接可到达的终端节点数。但后缀链接形成一棵树。v因此，我们需要计算后缀链接形成的树中从到根的路径上的终端顶点数。我们可以O(1)通过线性预处理及时完成（例如，可以显式构建这棵树，并使用一次深度优先搜索在线性时间内计算从根到任何顶点的路径上的总和）。我们还可以按正确的顺序处理顶点（例如，按高度递增的顺序）并执行类似的操作sum[v] += sum[suffix_link(v)]. 在这种情况下，我们甚至不需要实际构建这棵树。

该算法显然在输入大小的线性时间内有效（我们构建了 Aho-Corasick 自动机并在线性时间内计算“后缀链接路径”上的总和，然后我们像往常一样使用自动机）。

Answer 2

如果您想搜索一组字符串并且不喜欢依赖于出现的次数，请使用Rabin–Karp 。它的平均/最佳情况运行时间是O(n + m)，但其最坏情况时间是 O(nm)，其中n是文本m长度，是搜索模式的组合长度。

如果您只想搜索一个字符串，您可以使用Knuth–Morris–Pratt复杂度O(n + k)，其中n是文本k长度，是搜索模式长度。