字符串出现次数计数算法

Question

我很好奇，什么样的算法最有效（或者说是常用的）来计算一个字符串在一段文本中出现的次数。

根据我所了解的，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

你好，Hellnar，

你可以用一个简单的字典来计算一个字符串中字符出现的次数。这个方法就是一个计数算法，下面是一个例子：

"""
The counting algorithm is used to count the occurences of a character
in a string. This allows you to compare anagrams and strings themselves.
ex. animal, lamina a=2,n=1,i=1,m=1
"""

def count_occurences(str):
  occurences = {}
  for char in str:
    if char in occurences:
      occurences[char] = occurences[char] + 1
    else:
      occurences[char] = 1
  return occurences

  def is_matched(s1,s2):
    matched = True
    s1_count_table = count_occurences(s1)

    for char in s2:
      if char in s1_count_table and s1_count_table[char]>0:
      s1_count_table[char] -= 1
    else:
      matched = False
      break
    return matched

  #counting.is_matched("animal","laminar")

这个例子只会返回“真”或“假”，用来判断字符串是否匹配。要记住，这个算法会计算一个字符在字符串中出现的次数，这对于判断字母异位词（即字母相同但顺序不同的词）非常有用。

Answer 2

Boyer-Moore算法是个不错的选择，用来计算某个字符串出现的次数，因为它有一些额外的准备工作，但这些只需要做一次。这个算法在处理较长的字符串时效果更好，所以如果你要查找的字符串很短，比如“one”，它就不太合适。

如果你想计算重叠的情况，可以在找到一个匹配后，从下一个字符开始继续查找。如果你想忽略重叠的情况，就要在找到一个匹配后，跳过整个模式字符串的长度再开始查找。

如果你使用的编程语言里有像indexOf或strpos这样的方法，可以用来在一个字符串中查找另一个字符串，那就直接用它。如果发现速度太慢，那就换个更好的算法。

Answer 3

首先，是的，你可以用Boyer-Moore算法很高效地完成这个任务。不过，根据你问题的其他一些参数，可能还有更好的解决方案。

Aho-Corasick字符串匹配算法可以在目标字符串中找到一组模式字符串的所有出现位置，所需时间是O(m + n + z)，其中m是要搜索的字符串的长度，n是所有要匹配的模式字符串的总长度，z是找到的匹配总数。如果你只需要匹配一个字符串，这个时间复杂度是线性的。此外，它还可以找到同一个字符串的重叠出现情况。而且，如果你想检查一组字符串在某个源字符串中出现了多少次，只需调用一次这个算法。更棒的是，如果你要搜索的字符串集合不变，你可以先花O(n)的时间进行预处理，然后在O(m + z)的时间内找到所有匹配。

另一方面，如果你有一个源字符串和一个快速变化的子字符串集合需要搜索，你可能想用后缀树。在你要搜索的字符串上进行O(m)的预处理后，你可以在O(n)的时间内检查某个长度为n的子字符串在这个字符串中出现了多少次。

最后，如果你想找一个容易编码且麻烦少的方案，可以考虑Rabin-Karp算法。这个算法使用滚动哈希函数来查找字符串。大约十到十五行代码就能实现，没有预处理时间，对于普通文本字符串（文本很多但匹配少）来说，可以非常快速地找到所有匹配。

希望这些信息对你有帮助！