python - Python：如何计算子字符串的重叠出现

Question

我想计算像'aa'这样的字符串出现在'aaa'（或'aaaa'）中的次数。

最明显的代码给出了错误的（或者至少不是直观的）答案：

'aaa'.count('aa')
1 # should be 2
'aaaa'.count('aa')
2 # should be 3

有没有人有一个简单的方法来解决这个问题？

Answer 1

从str.count()文档：

返回[start, end] 范围内子字符串 sub的非重叠出现次数。可选参数 start 和 end 被解释为切片表示法。

所以不行。你得到了预期的结果。

如果要计算重叠匹配的数量，请使用regex：

>>> import re
>>> 
>>> len(re.findall(r'(a)(?=\1)', 'aaa'))
2

这会找到所有出现的a，然后是a。第二个a不会被捕获，因为我们使用了前瞻，这是零宽度断言。

Answer 2

haystack = "aaaa"
needle   = "aa"

matches  = sum(haystack[i:i+len(needle)] == needle 
               for i in xrange(len(haystack)-len(needle)+1))

# for Python 3 use range instead of xrange

Answer 3

该解决方案没有考虑重叠。

尝试这个：

big_string = "aaaa"
substring = "aaa"
count = 0 

for char in range(len(big_string)):
    count += big_string[char: char + len(subtring)] == substring

print count

Answer 4

您必须小心，因为您似乎在寻找不重叠的子字符串。为了解决这个问题，我会这样做：

len([s.start() for s in re.finditer('(?=aa)', 'aaa')])

如果你不关心子字符串开始的位置，你可以这样做：

len([_ for s in re.finditer('(?=aa)', 'aaa')])

虽然比我更聪明的人可能能够证明存在性能差异:)