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

Question

我想知道如何在线性时间内计算干草堆中每根针的出现次数。我想我应该使用Aho-Corasick算法，但我不希望时间复杂度取决于针的出现次数。

Answer 1

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

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

Answer 2

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

这个算法显然在输入大小的线性时间内工作(我们构建Aho-Corasick自动机，并在线性时间内计算“后缀链接路径”的和，然后我们像往常一样使用自动机)。