Поиск нескольких вхождений строки в строке в Python

Ответ 1

Используя регулярные выражения, вы можете использовать re.finditer, чтобы найти все (неперекрывающиеся) вхождения:

>>> import re
>>> text = 'Allowed Hello Hollow'
>>> for m in re.finditer('ll', text):
         print('ll found', m.start(), m.end())

ll found 1 3
ll found 10 12
ll found 16 18

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

>>> text = 'Allowed Hello Hollow'
>>> index = 0
>>> while index < len(text):
        index = text.find('ll', index)
        if index == -1:
            break
        print('ll found at', index)
        index += 2 # +2 because len('ll') == 2

ll found at  1
ll found at  10
ll found at  16

Это также работает для списков и других последовательностей.

Ответ 2

Я думаю, что вы ищете string.count

"Allowed Hello Hollow".count('ll')
>>> 3

Надеюсь, что это поможет ПРИМЕЧАНИЕ. Это только фиксирует неперекрывающиеся вхождения

Ответ 3

В примере списка используйте понимание:

>>> l = ['ll', 'xx', 'll']
>>> print [n for (n, e) in enumerate(l) if e == 'll']
[0, 2]

Аналогично для строк:

>>> text = "Allowed Hello Hollow"
>>> print [n for n in xrange(len(text)) if text.find('ll', n) == n]
[1, 10, 16]

это отобразит смежные прогоны "ll", которые могут быть или не быть такими, какие вы хотите:

>>> text = 'Alllowed Hello Holllow'
>>> print [n for n in xrange(len(text)) if text.find('ll', n) == n]
[1, 2, 11, 17, 18]

Ответ 4

FWIW, вот пара альтернатив, отличных от RE, которые я считаю более аккуратными, чем poke solution.

Первый использует str.index и проверяет на ValueError:

def findall(sub, string):
    """
    >>> text = "Allowed Hello Hollow"
    >>> tuple(findall('ll', text))
    (1, 10, 16)
    """
    index = 0 - len(sub)
    try:
        while True:
            index = string.index(sub, index + len(sub))
            yield index
    except ValueError:
        pass

Во вторых тестах используется str.find и проверяется дозорный элемент -1 с помощью iter:

def findall_iter(sub, string):
    """
    >>> text = "Allowed Hello Hollow"
    >>> tuple(findall_iter('ll', text))
    (1, 10, 16)
    """
    def next_index(length):
        index = 0 - length
        while True:
            index = string.find(sub, index + length)
            yield index
    return iter(next_index(len(sub)).next, -1)

Чтобы применить любую из этих функций к списку, кортежу или другим итерабельным строкам, вы можете использовать функцию более высокого уровня - один, который принимает функцию как один из своих аргументов - как этот:

def findall_each(findall, sub, strings):
    """
    >>> texts = ("fail", "dolly the llama", "Hello", "Hollow", "not ok")
    >>> list(findall_each(findall, 'll', texts))
    [(), (2, 10), (2,), (2,), ()]
    >>> texts = ("parallellized", "illegally", "dillydallying", "hillbillies")
    >>> list(findall_each(findall_iter, 'll', texts))
    [(4, 7), (1, 6), (2, 7), (2, 6)]
    """
    return (tuple(findall(sub, string)) for string in strings)

Ответ 5

Пример вашего списка:

In [1]: x = ['ll','ok','ll']

In [2]: for idx, value in enumerate(x):
   ...:     if value == 'll':
   ...:         print idx, value       
0 ll
2 ll

Если вам нужны все элементы в списке, содержащем 'll', вы также можете это сделать.

In [3]: x = ['Allowed','Hello','World','Hollow']

In [4]: for idx, value in enumerate(x):
   ...:     if 'll' in value:
   ...:         print idx, value
   ...:         
   ...:         
0 Allowed
1 Hello
3 Hollow

Ответ 6

>>> for n,c in enumerate(text):
...   try:
...     if c+text[n+1] == "ll": print n
...   except: pass
...
1
10
16

Ответ 7

Совершенно новый для программирования в целом и работы через онлайн-учебник. Меня также попросили сделать это, но только используя методы, которые я изучил до сих пор (в основном, строки и циклы). Не уверен, что это добавляет какое-либо значение здесь, и я знаю, что это не то, как вы это сделаете, но я получил его для работы с этим:

needle = input()
haystack = input()
counter = 0
n=-1
for i in range (n+1,len(haystack)+1):
   for j in range(n+1,len(haystack)+1):
      n=-1
      if needle != haystack[i:j]:
         n = n+1
         continue
      if needle == haystack[i:j]:
         counter = counter + 1
print (counter)

Ответ 8

Эта версия должна быть линейной по длине строки и должна быть точной, если последовательности не слишком повторяемы (в этом случае вы можете заменить рекурсию на цикл while).

def find_all(st, substr, start_pos=0, accum=[]):
    ix = st.find(substr, start_pos)
    if ix == -1:
        return accum
    return find_all(st, substr, start_pos=ix + 1, accum=accum + [ix])

Определение списка bstpierre является хорошим решением для коротких последовательностей, но выглядит как квадратичная сложность и никогда не заканчивается на длинном тексте, который я использовал.

findall_lc = lambda txt, substr: [n for n in xrange(len(txt))
                                   if txt.find(substr, n) == n]

Для случайной строки нетривиальной длины две функции дают один и тот же результат:

import random, string; random.seed(0)
s = ''.join([random.choice(string.ascii_lowercase) for _ in range(100000)])

>>> find_all(s, 'th') == findall_lc(s, 'th')
True
>>> findall_lc(s, 'th')[:4]
[564, 818, 1872, 2470]

Но квадратичная версия примерно в 300 раз медленнее

%timeit find_all(s, 'th')
1000 loops, best of 3: 282 µs per loop

%timeit findall_lc(s, 'th')    
10 loops, best of 3: 92.3 ms per loop

Ответ 9

#!/usr/local/bin python3
#-*- coding: utf-8 -*-

main_string = input()
sub_string = input()

count = counter = 0

for i in range(len(main_string)):
    if main_string[i] == sub_string[0]:
        k = i + 1
        for j in range(1, len(sub_string)):
            if k != len(main_string) and main_string[k] == sub_string[j]:
                count += 1
                k += 1
        if count == (len(sub_string) - 1):
            counter += 1
        count = 0

print(counter) 

Эта программа подсчитывает количество всех подстрок, даже если они перекрываются без использования регулярных выражений. Но это наивная реализация, и для достижения лучших результатов в худшем случае рекомендуется пройти через суффикс-дерево, KMP и другие структуры и алгоритмы сопоставления строк.

Ответ 10

Вот моя функция для поиска нескольких вхождений. В отличие от других решений здесь, он поддерживает необязательные начальные и конечные параметры для нарезки, точно так же, как str.index:

def all_substring_indexes(string, substring, start=0, end=None):
    result = []
    new_start = start
    while True:
        try:
            index = string.index(substring, new_start, end)
        except ValueError:
            return result
        else:
            result.append(index)
            new_start = index + len(substring)

Ответ 11

Простой итеративный код, который возвращает список индексов, в которых происходит подстрока.

        def allindices(string, sub):
           l=[]
           i = string.find(sub)
           while i >= 0:
              l.append(i)
              i = string.find(sub, i + 1)
           return l

Ответ 12

Вы можете разделить, чтобы получить относительные позиции, а затем суммировать последовательные числа в списке и добавить (порядок длины строки * порядок вхождения) в то же время, чтобы получить нужные индексы строк.

>>> key = 'll'
>>> text = "Allowed Hello Hollow"
>>> x = [len(i) for i in text.split(key)[:-1]]
>>> [sum(x[:i+1]) + i*len(key) for i in range(len(x))]
[1, 10, 16]
>>> 

Ответ 13

Это можно сделать в одной строке с использованием списков:

example = "a test am I"
indicies = [index for index, value in enumerate(example) if value == "a"]
print(indices)

 >>> [0, 7]

Аналогичная техника работает для списков:

example = ["a", "b", "c", "a", "d"]
indices = [index for index, value in enumerate(example) if value =="a"]
print(indices)

>>> [0, 3]

Ответ 14

Может быть, не так питонический, но несколько более понятный. Он возвращает позицию слова в исходной строке.

def retrieve_occurences(sequence, word, result, base_counter):
     indx = sequence.find(word)
     if indx == -1:
         return result
     result.append(indx + base_counter)
     base_counter += indx + len(word)
     return retrieve_occurences(sequence[indx + len(word):], word, result, base_counter)

Ответ 15

Эта ссылка объясняет, как делать все это в O (n) и включает в себя также решение на питоне.

Если вы подойдете дальше вниз к 'деревья суффикса, вы сможете сделать то же самое, если бы у вас был один большой string, но хотел найти в нем 1000s шаблонов.

Ответ 16

Я думаю, что нет необходимости тестировать длину текста; просто продолжайте искать, пока не найдете ничего, что можно было бы найти. Вот так:

    >>> text = 'Allowed Hello Hollow'
    >>> place = 0
    >>> while text.find('ll', place) != -1:
            print('ll found at', text.find('ll', place))
            place = text.find('ll', place) + 2


    ll found at 1
    ll found at 10
    ll found at 16

Ответ 17

Вы также можете сделать это с учетом условного списка следующим образом:

string1= "Allowed Hello Hollow"
string2= "ll"
print [num for num in xrange(len(string1)-len(string2)+1) if string1[num:num+len(string2)]==string2]
# [1, 10, 16]