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

#python #строки

Вхождение подстрок в строку обычно находится примерно таким образом: 

print stroka.count("podstroka")


Проблема этого подхода в том, что, если у нас стоит условие найти вхождения перекрывающихся
подстрок, оно работает неправильно. 

Например, есть строка "avava avavava" и надо найти вхождения подстроки "vav". Код
выше даст результат 2, однако, по логике, должно быть 3, так как в начале есть vav,
потом два вхождения в vavav. 

Как это правильно реализовать?
    

Ответы

Ответ 1

Вот версия, которая избегает излишнего копирования входной строки:
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()
метод.


Ответ 2

Можно, например, через регеспы и "lookahead":
# -*- coding: utf-8 -*-
import re

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

print count_substrings('avavrewwevavavewrewrew vavvavav ', 'vav') # == 6

Причем на мелких строках он медленней, чем предложенные выше варианты, но вот начиная
уже с 100 символов начинает сильно выигрывать. Я потестировал скорость, тут результаты.
Регекспы в 1.23 раза быстрее. С увеличением строки эта разница будет возрастать.


Ответ 3

Если на скорую руку, то можно так:
s = 'avavrewwevavavewrewrew'
ind = 1
count = 0
f = 'vav'
while ind != -1:
    ind = s.find(f)
    if ind >= 0:
        count += 1
    s = s[ind+1:]
print count

Суть в отбрасывании первого символа подстроки, чтобы он её больше не находил.


Ответ 4

@spirit только ind >= 0.
s = 'avavrewwevavavewrewrew'
ind = 1
count = 0
f = 'vav'
while ind != -1:
    ind = s.find(f)
    if ind >= 0:
        count += 1
    s = s[ind+1:]
print count


Ответ 5

def greed_count(str, substr):
    return 0 if len(str) < len(substr) else str.startswith(substr) + greed_count(str[1:],
substr)

print(greed_count('avavrewwevavavewrewrew', 'vav'))