Wyszukiwanie podsekwencji dokonuje się wyspecjalizowanym algorytmem takim jak algorytm Knutha-Morrisa-Pratta, które są wydajniejsze niż naiwne przeszukiwanie takie jak podał @Spine. Druga edycja książki Python receptury podaje następującą implementację:
def KnuthMorrisPratt(text, pattern):
''' Yields all starting positions of copies of subsequence 'pattern'
in sequence 'text' -- each argument can be any iterable.
At the time of each yield, 'text' has been read exactly up to and
including the match with 'pattern' that is causing the yield. '''
# ensure we can index into pattern, and also make a copy to protect
# against changes to 'pattern' while we're suspended by `yield'
pattern = list(pattern)
length = len(pattern)
# build the KMP "table of shift amounts" and name it 'shifts'
shifts = [1] * (length + 1)
shift = 1
for pos, pat in enumerate(pattern):
while shift <= pos and pat != pattern[pos-shift]:
shift += shifts[pos-shift]
shifts[pos+1] = shift
# perform the actual search
startPos = 0
matchLen = 0
for c in text:
while matchLen == length or matchLen >= 0 and pattern[matchLen] != c:
startPos += shifts[matchLen]
matchLen -= shifts[matchLen]
matchLen += 1
if matchLen == length: yield startPos
Zastosowanie:
lista_wejsciowa = [12,23,24,25,65,64,63,]
ciag_do_znalezienia = [25,65,64]
for i in KnuthMorrisPratt(lista_wejsciowa, ciag_do_znalezienia):
print(i)
Jest to iterator, zatem zwraca nie tylko pierwszy, ale i kolejne wystąpienia podciągu. Policzenie ile razy wystąpił podciąg sprowadza się do policzenia ile wyników zwrócono:
print(len(list(KnuthMorrisPratt(lista_wejsciowa, ciag_do_znalezienia))))