Python: how to count overlapping occurrences of a substring [duplicate]

Question

I wanted to count the number of times that a string like 'aa' appears in 'aaa' (or 'aaaa').

The most obvious code gives the wrong (or at least, not the intuitive) answer:

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

Does anyone have a simple way to fix this?

Answer 1

From str.count() documentation:

Return the number of non-overlapping occurrences of substring sub in the range [start, end]. Optional arguments start and end are interpreted as in slice notation.

So, no. You are getting the expected result.

If you want to count number of overlapping matches, use regex:

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

This finds all the occurrence of a, which is followed by a. The 2nd a wouldn't be captured, as we've used look-ahead, which is zero-width assertion.

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