String count with overlapping occurrences [closed]

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

Какой наилучший способ подсчитать количество вхождений данной строки, включая перекрытие в 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')

Этот метод возвращает 5.

Есть ли лучший способ в Python?

Переведено автоматически

Ответ 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

Ответ 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

Ответ 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

Ответ 4

В Python 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