|
||
Vyhledávání se provádí zleva doprava, ale posun vzoru je mnohem efektivnější než u Brute Force.
Při neshodě hledáme maximální možný posun a snažíme se neporovnávat znovu části řetězce, u kterých jsme schopni dopředu určit, že jsou shodné (viz příklad 
).
Zavádí se tzv. chybová funkce (failure function) F(k), kde k je číslo pozice před neshodou (tedy pokud je pozice, kde se znaky neshodují j, pak k = j -1).
F(k) je definována jako délka nejdelšího prefixu P[0..k], který je zároveň suffixem P[1..k]. Tuto funkci pro hledaný vzor opět předpočítáme a výsledek uložíme například do pole.
Porovnáváme řetězce od jejich začátku. Pokud se na místě j znaky liší, posuneme řetězec P tak, že začíná na místě, kde předtím začínal nejdelší suffix P[1..k], který je zároveň prefixem P[0..k] a porovnávání pokračuje za tímto prefixems Ve skutečnosti samozřejmě řetězec P neposouváme, ale nastavíme index aktuální porovnávací pozice tak, aby to vypadalo, že jsme řetězec P posunuli na uvedené místo. Tento index odpovídá právě výše definované chybové funkci F(k).
Příklad
public static int[] computeFail(String pattern) {
int fail[] = new int[pattern.length()];
fail[0] = 0;
int m = pattern.length();
int j = 0;
int i = 1;
while (i < m) {
if (pattern.charAt(j) == pattern.charAt(i)) { //j+1 chars match
fail[i] = j + 1;
i++;
j++;
}
else
if (j > 0) // j follows matching prefix
j = fail[j-1];
else { //no match
fail[i] = 0;
i++;
}
}
return fail;
} // end of computeFail()
public static int kmpMatch(String text,
{
int n = text.length();
int m = pattern.length();
int fail[] = computeFail(pattern);
int i=0;
int j=0;
while (i < n) {
if (pattern.charAt(j) == text.charAt(i)) {
if (j == m - 1)
return i - m + 1; // match
i++;
j++;
}
else
if (j > 0)
j = fail[j-1];
else
i++;
}
return -1; // no match
} // end of kmpMatch()
Časová složitost celého algoritmu je tedy O(m+n), což je výrazně lepší než u naivního algoritmu. Algoritmus je vhodný pro vyhledávání v souborech, protože se nikdy nevrací zpět ve vyhledávacím řetězci.