Поиск подстроки внахлест

overlap_substrings.py

# -*- coding: utf-8 -*-
import re

def count_substrings_re(string, substring):
    substring_re = '(?=(%s))' %  re.escape(substring)
    return len(re.findall(substring_re, string))

def count_substrings(s, f):
    ind = 1
    count = 0
    while ind != -1:
        ind = s.find(f)
        if ind >= 0:
            count += 1
        s = s[ind+1:]
    return count

if __name__ == '__main__':
    import timeit
    big_string = "avavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvava vavavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvavav";
    print len(big_string)
    print(timeit.timeit(
            "count_substrings_re('%s', 'vav')" % big_string,
            setup="from __main__ import count_substrings_re"
        )
    )
    print(timeit.timeit(
            "count_substrings('%s', 'vav')" % big_string,
            setup="from __main__ import count_substrings"
        )
    )




# Выдает
#279
#20.2662341595
#26.177601099

Добавил свой, немного оптимизированный вариант
https://gist.github.com/ReinRaus/8846dc49fc532d4e1b28