Каков наилучший способ подсчета количества вхождений данной строки, включая перекрытие в 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
?
Или есть лучший способ в Python?
Ну, это может быть быстрее, потому что это сравнение в C:
def occurrences(string, sub):
count = start = 0
while True:
start = string.find(sub, start) + 1
if start > 0:
count+=1
else:
return count
>>> 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
Вы также можете попробовать использовать новый модуль регулярного выражения 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
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
s = "bobobob"
sub = "bob"
ln = len(sub)
print(sum(sub == s[i:i+ln] for i in xrange(len(s)-(ln-1))))
Эта функция (другое решение!) получает шаблон и текст. Возвращает список со всей подстрокой, расположенной в их и их положениях.
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)]
[('Bana', 0), ('nana', 2), ('fana', 7), ('fana', 15)]
Мой ответ на вопрос bob о курсе:
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
def count_substring(string, sub_string):
count = 0
for pos in range(len(string)):
if string[pos:].startswith(sub_string):
count += 1
return count
Это может быть самый простой способ.
Вот мое решение edx MIT "find bob" * (* найти количество вхождений "bob" в строке с именем s), которая в основном подсчитывает перекрывающиеся вхождения данной подстанции:
s = 'azcbobobegghakl'
count = 0
while 'bob' in s:
count += 1
s = s[(s.find('bob') + 2):]
print "Number of times bob occurs is: {}".format(count)
Это можно решить с помощью регулярного выражения.
import re
def function(string, sub_string):
match = re.findall('(?='+sub_string+')',string)
return len(match)
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
Выше кода просто повторяется по всей строке один раз и продолжает проверять, начинается ли какая-либо строка с конкретной подсчитанной подстрокой.
Довольно питоническим способом было бы использовать здесь понимание списков, хотя это, вероятно, было бы не самым эффективным.
sequence = 'abaaadcaaaa'
substr = 'aa'
counts = sum([
sequence.startswith(sub, i) for i in range(len(sequence))
])
print(counts) # 5
Список будет [False, False, True, False, False, False, True, True, False, False] как он проверяет все индексы в строке, и поскольку int(True) == 1, sum дает нам общее число из матчей.
def count_overlaps (string, look_for):
start = 0
matches = 0
while True:
start = string.find (look_for, start)
if start < 0:
break
start += 1
matches += 1
return matches
print count_overlaps ('abrabra', 'abra')
Функция, которая принимает в качестве входных данных две строки и подсчитывает, сколько раз подстрока происходит в строке, включая перекрытия. Чтобы проверить, является ли sub подстрокой, я использовал оператор in.
def count_Occurrences(string, sub):
count=0
for i in range(0, len(string)-len(sub)+1):
if sub in string[i:i+len(sub)]:
count=count+1
print 'Number of times sub occurs in string (including overlaps): ', count
Для дублированного question я решил считать его 3 на 3 и сравнить строку, например.
counted = 0
for i in range(len(string)):
if string[i*3:(i+1)*3] == 'xox':
counted = counted +1
print counted
Альтернатива, очень близкая к принятому ответу, но использующая while как тест if вместо включения if внутри цикла:
def countSubstr(string, sub):
count = 0
while sub in string:
count += 1
string = string[string.find(sub) + 1:]
return count;
Это позволяет избежать while True: и, по моему мнению, немного чище
Если строки велики, вы хотите использовать Rabin-Karp, вкратце:
Это еще один пример использования str.find() но многие ответы делают его более сложным, чем необходимо:
def occurrences(text, sub):
c, n = 0, text.find(sub)
while n != -1:
c += 1
n = text.find(sub, n+1)
return c
In []:
occurrences('1011101111', '11')
Out[]:
5
Данный
sequence = '1011101111'
sub = "11"
Код
В этом конкретном случае:
sum(x == tuple(sub) for x in zip(sequence, sequence[1:]))
# 5
В более общем плане это
windows = zip(*([sequence[i:] for i, _ in enumerate(sequence)][:len(sub)]))
sum(x == tuple(sub) for x in windows)
# 5
или распространяются на генераторы:
import itertools as it
iter_ = (sequence[i:] for i, _ in enumerate(sequence))
windows = zip(*(it.islice(iter_, None, len(sub))))
sum(x == tuple(sub) for x in windows)
альтернатива
Вы можете использовать more_itertools.locate:
import more_itertools as mit
len(list(mit.locate(sequence, pred=lambda *args: args == tuple(sub), window_size=len(sub))))
# 5
Простой способ подсчета вхождения подстроки состоит в использовании count():
>>> s = 'bobob'
>>> s.count('bob')
1
Вы можете использовать replace() чтобы найти перекрывающиеся строки, если вы знаете, какая часть будет перекрываться:
>>> s = 'bobob'
>>> s.replace('b', 'bb').count('bob')
2
Обратите внимание, что помимо статичности, есть и другие ограничения:
>>> s = 'aaa'
>>> count('aa') # there must be two occurrences
1
>>> s.replace('a', 'aa').count('aa')
3
def occurance_of_pattern(text, pattern):
text_len , pattern_len = len(text), len(pattern)
return sum(1 for idx in range(text_len - pattern_len + 1) if text[idx: idx+pattern_len] == pattern)
Если вы хотите подсчитать количество перестановок длины 5 (отрегулируйте, если хотите для разных длин):
def MerCount(s):
for i in xrange(len(s)-4):
d[s[i:i+5]] += 1
return d
sum([ 1 for _ in range(len(string)-len(str_to_search_for)+1) if string[_:_+len(str_to_search_for)] == str_to_search_for])
В понимании списка мы перемещаем большую строку по одной позиции за раз с скользящим окном длины меньшей строки. Мы можем вычислить скользящее число, вычитая длину меньшей строки из большей строки. Для каждого слайда мы сравниваем ту часть большей строки с нашей меньшей строкой и генерируем 1 в списке, если совпадение найдено. Сумма всех этих 1 в списке даст нам общее количество найденных совпадений.