Поиск последовательности элементов в списке

Question

Есть ли простой способ поиска последовательности строк в списке?Например:

testlist = [a,b,c,d,e,f,g,a,b,c,d,j,k,j] 

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

Answer 1

Есть много хороших алгоритмов поиска строк : KMP, Бойер-Мур, Рабин-Карп.Вы можете использовать встроенную функцию str.index на ''.join(L), если имеете дело с символами (str.index реализует алгоритм Бойера-Мура в CPython: https://github.com/python/cpython/blob/3.7/Objects/stringlib/fastsearch.h).

Но в большинстве случаев наивныйалгоритм достаточно хорош. Проверьте каждый индекс haystack, чтобы найти needle:

>>> a, b, c, d, e, f, g, j, k = [object() for _ in range(9)]
>>> haystack = [a, b, c, d, e, f, g, a, b, c, d, j, k, j]
>>> needle = [a, b, c]
>>> for i in range(len(haystack)-len(needle)+1):
...     if haystack[i:i+len(needle)] == needle:
...             print(i)
... 
0
7

Сложность O (| стог сена | * | needle |).