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

Question

Как найти несколько вхождений строки в строке в Python?Учтите это:

>>> text = "Allowed Hello Hollow"
>>> text.find("ll")
1
>>> 

Итак, первое вхождение ll соответствует 1, как и ожидалось.Как мне найти следующее вхождение?

Тот же вопрос действителен для списка.Подумайте:

>>> x = ['ll', 'ok', 'll']

Как мне найти все ll с их индексами?

Answer 1

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

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)

Answer 2

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

>>> 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]
>>> 

Answer 3

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

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

Answer 4

Вот моя функция для поиска нескольких вхождений.В отличие от других решений здесь, он поддерживает дополнительные параметры начала и конца для нарезки, как 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)

Answer 5

#!/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) 

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

Answer 6

Эта версия должна быть линейной по длине строки и должна подойти, если последовательности не слишком повторяются (в этом случае вы можете заменить рекурсию циклом 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