计算子串的数量
我想问是否有一种算法可以在 O(n) 时间内统计字符串中子串离散出现的次数。
I would like to ask if there is an algorithm for counting the number of discrete occurencies of a substring in a string in O(n) time.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
[编辑 2013 年 11 月 17 日：计算叶节点。谢谢 Vinicius Pinto！]
您可以在线性时间内在文本上构建后缀树 。然后，在后缀树中搜索你的子字符串；当找到它时，计算匹配节点下方的叶节点数。对于长度为 m 的子字符串出现 k 次，这是 O(m + k)（添加 n 项用于构建后缀树）。或者，您可以使用深度优先遍历来预先计算树中每个节点的后代数量——这将给出 O(m) 查询。
对于大型文本，后缀数组在实践中通常比后缀树更快，尽管搜索单个长度为 m 的字符串从 O(m) 下降到 O(m log m)。在这种情况下，特定子字符串的所有出现都将作为后缀数组中的连续块出现，因此该块的宽度就是出现的次数。
[EDIT 17/11/2013: Count the leaf nodes. Thanks Vinicius Pinto!]
You can build a suffix tree on the text in linear time. Then, search for your substring in the suffix tree; when you find it, count the number of leaf nodes beneath the matching node. This is O(m + k) for a substring of length m that appears k times (add an n term for building the suffix tree). Or, you can precalculate the number of descendants for each node in the tree using a depth-first traversal -- this will give O(m) queries.
For large texts, suffix arrays are often faster than suffix trees in practice, despite searching for a single length-m string dropping from O(m) to O(m log m). In this case, all occurrences of a particular substring will appear as a contiguous block in the suffix array, so the width of this block is the number of occurrences.
您可以使用KMP 算法< /a> 并修改它以增加计数器而不是返回。
另一种可能性是 Rabin-Karp 算法，但是这依赖于哈希，所以你要么接受误报的可能性，同时保持复杂性为线性，或者接受二次复杂性的可能性，同时保持结果 100% 正确。
You can use the KMP Algorithm and modify it to increment a counter instead of returning.
Another possibility is the Rabin-Karp algorithm, however this relies on hashing, so you either have to accept the possibility of false positives while keeping the complexity linear, or accept the possibility of quadratic complexity while keeping the results 100% correct.