Подсчёт вхождений перекрывающейся подстроки в строку

Вхождение подстрок в строку обычно находится примерно таким образом:
print stroka.count("podstroka")
Проблема этого подхода в том, что, если у нас стоит условие найти вхождения перекрывающихся подстрок, оно работает неправильно.
Например, есть строка "avava avavava" и надо найти вхождения подстроки "vav". Код выше даст результат 2, однако, по логике, должно быть 3, так как в начале есть vav, потом два вхождения в vavav.
Как это правильно реализовать?

Ответ

Вот версия, которая избегает излишнего копирования входной строки: def count_overlapping_substrings(haystack, needle): count = 0 i = -1 while True: i = haystack.find(needle, i+1) if i == -1: return count count += 1
print(count_overlapping_substrings('avavrewwevavavewrewrew vavvavav ', 'vav')) # -> 6 Время исполнения -- квадратичное, как и у других вариантов, которые используют str.find() метод.