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

Рейтинг: 11Ответов: 3Опубликовано: 03.03.2015

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

print stroka.count("podstroka")

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

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

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

python строки
Источник: Stack Overflow на русском

Ответы

▲ 9Принят

Вот версия, которая избегает излишнего копирования входной строки:

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() метод.

▲ 5

Можно, например, через регеспы и "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 раза быстрее. С увеличением строки эта разница будет возрастать.

▲ 4

Если на скорую руку, то можно так:

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

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