python - 字符串出现次数计数算法

Question

我很好奇计算文本 block 中字符串出现次数的最有效(或最常用)算法是什么。

来 self read , Boyer–Moore 字符串搜索算法是字符串搜索的标准，但我不确定以有效方式计算出现次数是否与搜索字符串相同。

在 Python 中，这就是我想要的:

text_chunck = "one two three four one five six one"
occurance_count(text_chunck, "one") # gives 3.

编辑:似乎 python str.count 就是这样一种方法；但是，我无法找到它使用的算法。

Answer 1

对于初学者来说，是的，您可以通过 Boyer-Moore 非常有效地完成此任务。但是，根据您问题的其他一些参数，可能会有更好的解决方案。

The Aho-Corasick string matching algorithm 将在目标字符串中找到所有出现的 set 模式字符串，并在时间 O(m + n + z) 内完成，其中 m 是要搜索的字符串的长度， n 是要匹配的所有模式的组合长度，z 是产生的匹配总数。如果您只有一个字符串要匹配，则这与源字符串和目标字符串的大小成线性关系。它还会找到相同字符串的重叠出现。此外，如果你想检查一组字符串在某个源字符串中出现了多少次，你只需要调用一次算法。在此之上，如果您要搜索的字符串集永远不会改变，您可以将 O(n) 工作作为预处理时间，然后在 O(m + z) 中找到所有匹配项。

另一方面，如果您有一个源字符串和一组快速变化的子字符串要搜索，您可能需要使用 suffix tree 。使用要搜索的字符串的 O(m) 预处理时间，您可以在每个子字符串的 O(n) 时间内检查长度为 n 的特定子字符串在字符串中出现了多少次。

最后，如果您正在寻找可以轻松编写代码且麻烦最少的东西，您可能需要考虑查看 Rabin-Karp 算法，它使用 roling 哈希函数来查找字符串。这可以用大约 10 到 15 行代码编写，没有预处理时间，并且对于普通文本字符串(大量文本，很少匹配)可以非常快速地找到所有匹配项。

希望这对您有所帮助!