количество строк с перекрывающимися вхождениями

Question

Какой лучший способ подсчитать количество вхождений данной строки, включая перекрытие в python? это самый очевидный способ:

def function(string, str_to_search_for):
      count = 0
      for x in xrange(len(string) - len(str_to_search_for) + 1):
           if string[x:x+len(str_to_search_for)] == str_to_search_for:
                count += 1
      return count


function('1011101111','11')
returns 5

или есть лучший способ в питоне?

Answer 1

Ну, это может быть быстрее, так как оно выполняет сравнение в C:

def occurrences(string, sub):
    count = start = 0
    while True:
        start = string.find(sub, start) + 1
        if start > 0:
            count+=1
        else:
            return count

Answer 2

>>> import re
>>> text = '1011101111'
>>> len(re.findall('(?=11)', text))
5

Если вы не хотите загружать весь список совпадений в память, это никогда не будет проблемой! Вы могли бы сделать это, если бы вы действительно хотели:

>>> sum(1 for _ in re.finditer('(?=11)', text))
5

Как функция (re.escape гарантирует, что подстрока не мешает регулярному выражению):

>>> def occurrences(text, sub):
        return len(re.findall('(?={0})'.format(re.escape(sub)), text))

>>> occurrences(text, '11')
5

Answer 3

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

import regex as re

def count_overlapping(text, search_for):
    return len(re.findall(search_for, text, overlapped=True))

count_overlapping('1011101111','11')  # 5

Answer 4

Python's str.count считает непересекающиеся подстроки:

In [3]: "ababa".count("aba")
Out[3]: 1

Вот несколько способов подсчета перекрывающихся последовательностей, я уверен, что есть еще много:)

Регулярные выражения прогнозирования

Как найти совпадающие совпадения с регулярным выражением?

In [10]: re.findall("a(?=ba)", "ababa")
Out[10]: ['a', 'a']

Генерация всех подстрок

In [11]: data = "ababa"
In [17]: sum(1 for i in range(len(data)) if data.startswith("aba", i))
Out[17]: 2

Answer 5

Как найти шаблон в другой строке с перекрытием

Эта функция (другое решение!) Получает шаблон и текст. Возвращает список со всеми подстроками, расположенными в и их позициями.

def occurrences(pattern, text):
    """
    input: search a pattern (regular expression) in a text
    returns: a list of substrings and their positions 
    """
    p = re.compile('(?=({0}))'.format(pattern))
    matches = re.finditer(p, text)
    return [(match.group(1), match.start()) for match in matches]

print (occurrences('ana', 'banana'))
print (occurrences('.ana', 'Banana-fana fo-fana'))

[('ana', 1), ('ana', 3)]
[(«Бана», 0), («Нана», 2), («Фана», 7), («Фана», 15)]

Answer 6

s = "bobobob"
sub = "bob"
ln = len(sub)
print(sum(sub == s[i:i+ln] for i in xrange(len(s)-(ln-1))))

Answer 7

Мой ответ на вопрос Боба о курсе:

s = 'azcbobobegghaklbob'
total = 0
for i in range(len(s)-2):
    if s[i:i+3] == 'bob':
        total += 1
print 'number of times bob occurs is: ', total

Answer 8

def count_substring(string, sub_string):
    count = 0
    for pos in range(len(string)):
        if string[pos:].startswith(sub_string):
            count += 1
    return count

Это может быть самый простой способ.

Answer 9

def count_substring(string, sub_string):
    counter = 0
    for i in range(len(string)):
        if string[i:].startswith(sub_string):
        counter = counter + 1
    return counter

Приведенный выше код просто зацикливается по всей строке один раз и продолжает проверять, начинается ли какая-либо строка с конкретной подсчитываемой подстроки.

Answer 10

Это можно решить с помощью регулярных выражений.

import re
def function(string, sub_string):
    match = re.findall('(?='+sub_string+')',string)
    return len(match)