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

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

  • проблема при передаче данных с использованием объекта сеанса SQLAlchemy в цикле
  • Как преобразовать строку в функцию в python?
  • Добавление NumPy и добавление Python
  • Борьба за установку пигтта с пипсом
  • Усечение юникода, чтобы он соответствовал максимальному размеру при кодировании для переноса
  • Python - как конвертировать Unicode имя файла в CP437?
  • Испускание спецификаций пространства имен с ElementTree в Python
  • Python API Диска Google - список всего дерева файлов дисков
  • 16 Solutions collect form web for “количество строк с перекрывающимися вхождениями”

    Ну, это может быть быстрее, так как это сравнение в 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 

    Вы также можете попробовать использовать новый модуль regex 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)))) 

    Мой ответ на вопрос 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 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)]

    Вот мое решение 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_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 

    Для дублированного вопроса я решил посчитать его 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 , вкратце:

    • развертки окна размера подстроки, перемещение по строке
    • хэш с O (1) служебными данными для добавления и удаления (т.е. перемещение на 1 символ)
    • реализованный в C или полагающийся на pypy
     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 

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

    Если вы хотите подсчитать количество перестановок длины 5 (отрегулируйте, если хотите для разных длин):

     def MerCount(s): for i in xrange(len(s)-4): d[s[i:i+5]] += 1 return d 
    Python - лучший язык программирования в мире.