KMP, prefix function ve Z algoritması

Naif pattern search mismatch'te yeniden çok harf karşılaştırabilir. KMP, pattern'ın prefix function'ını kullanır: pi[i], pattern[0:i+1]'in kendisi olmayan en uzun prefix=suffix uzunluğudur. Mismatch'te j=pi[j−1] ile daha kısa uygun prefix'e döner; metin indeksini geri almaz.

“aba” için pi=[0,0,1]. Match tamamlanınca overlapping sonuçları bulmak için j tekrar pi[j−1] olur. Z[i] string'in i konumundan başlayan suffix'i ile prefix'inin ortak uzunluğudur; bir [l,r) eşleşme kutusunu kullanarak doğrusal hesaplanır. Pattern+separator+text yaklaşımında separator girdide bulunmamalı veya token seviyesinde özel sentinel seçilmelidir.

Unicode normalization yapılmamış iki görünüşte aynı metin farklı code point dizileri olabilir. Bu algoritmalar verilen sembol dizisini eşler, linguistik anlamı çözmez. Boş pattern davranışı ve sonuç indekslerinin byte/code point olması açıkça belirlenmelidir.

def kmp(text, pattern):
    if not pattern: return list(range(len(text)+1))
    pi=[0]*len(pattern); j=0
    for i in range(1,len(pattern)):
        while j and pattern[i] != pattern[j]: j=pi[j-1]
        if pattern[i] == pattern[j]: j+=1
        pi[i]=j
    out=[]; j=0
    for i,c in enumerate(text):
        while j and c != pattern[j]: j=pi[j-1]
        if c == pattern[j]: j+=1
        if j == len(pattern): out.append(i-j+1); j=pi[j-1]
    return out
assert kmp("ababa","aba") == [0,2]