Algorytm wynaleziony w 1977 roku przez Donalda Knutha i Vaughana Pratta i niezależnie przez Jamesa H. Morrisa.
Algorytm stosowany jest do przeszukiwania tekstu. Jego “mocą” jest to, że już sam wzorzec może zawierać informacje przydatne do tego gdzie dalej rozpocząć przeszukiwanie.
Dzięki temu oszczędza trochę czasu w poszukiwaniu. Co ciekawe, a nie zawsze można znaleźć o tym łatwo informacje, do algorytmu można użyć grafów. Np. dla wzorca abaa można zbudować graf jak niżej:
Najwięcej można dowiedzieć się jak działa algorytm oglądając jego implementację, która zamieszczam poniżej.
def KMPSearch(pat, txt):
M = len(pat)
N = len(txt)
# create lps[] that will hold the longest prefix suffix
# values for pattern
lps = [0]*M
j = 0 # index for pat[]
# Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps)
i = 0 # index for txt[]
while i < N:
if pat[j] == txt[i]:
i += 1
j += 1
if j == M:
print "Found pattern at index " + str(i-j)
j = lps[j-1]
# mismatch after j matches
elif i < N and pat[j] != txt[i]:
# Do not match lps[0..lps[j-1]] characters,
# they will match anyway
if j != 0:
j = lps[j-1]
else:
i += 1
def computeLPSArray(pat, M, lps):
len = 0 # length of the previous longest prefix suffix
lps[0] # lps[0] is always 0
i = 1
# the loop calculates lps[i] for i = 1 to M-1
while i < M:
if pat[i]== pat[len]:
len += 1
lps[i] = len
i += 1
else:
# This is tricky. Consider the example.
# AAACAAAA and i = 7. The idea is similar
# to search step.
if len != 0:
len = lps[len-1]
# Also, note that we do not increment i here
else:
lps[i] = 0
i += 1
# This code is contributed by Bhavya Jain
Istnieje kilka innych algorytmów przeszukania tekstu a jednym z nich jest algorytm pomagający wyszukiwać plagiaty. Nazywa się on algorytmem Karpa-Rabina i dzięki swojej logice nie jest wrażliwy na dokładne dopasowania wzorca do szukanego tekstu.