algorithm
Algoritme van Knuth Morris Pratt (KMP)
Zoeken…
Invoering
De KMP is een patroonvergelijkingsalgoritme dat zoekt naar het voorkomen van een "woord" W binnen een hoofd "tekststring" S door de observatie te gebruiken dat wanneer er een mismatch optreedt, we voldoende informatie hebben om te bepalen waar de volgende match kan beginnen. gebruik maken van deze informatie om te voorkomen dat het afstemmen van de personages die we kennen zullen toch match.The worst case complexiteit voor het zoeken van een patroon gereduceerd tot O (n).
KMP-Voorbeeld
Algoritme
Dit algoritme is een proces in twee stappen. Eerst maken we een hulparray lps [] en gebruiken deze array vervolgens om het patroon te doorzoeken.
Voorbewerking :
- We verwerken het patroon vooraf en maken een hulparray lps [] die wordt gebruikt om tekens over te slaan tijdens het matchen.
- Hier geeft lps [] het langste juiste voorvoegsel aan, dat ook een achtervoegsel is. Een geschikt voorvoegsel is een voorvoegsel waarin de hele tekenreeks niet is opgenomen. Voorvoegsels van tekenreeks ABC zijn bijvoorbeeld "" , "A" , "AB" en "ABC" . Juiste voorvoegsels zijn "" , "A" en "AB" . Achtervoegsels van de tekenreeks zijn "" , "C" , "BC" en "ABC" .
Zoeken
We blijven de tekens txt [i] en pat [j] matchen en blijven i en j ophogen terwijl pat [j] en txt [i] blijven matchen.
Wanneer we een mismatch zien, weten we dat tekens pat [0..j-1] overeenkomen met txt [i-j + 1 ... i-1] . We weten ook dat lps [j-1] het aantal tekens van pat is [0 ... j-1] die zowel het juiste voorvoegsel als het achtervoegsel zijn. Hieruit kunnen we concluderen dat we deze lps [j-1] tekens niet hoeven te matchen met txt [ij ... i-1] omdat we weten dat deze tekens komt toch overeen.
Implementatie in Java
public class KMP {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "abcabdabc";
String pattern = "abc";
KMP obj = new KMP();
System.out.println(obj.patternExistKMP(str.toCharArray(), pattern.toCharArray()));
}
public int[] computeLPS(char[] str){
int lps[] = new int[str.length];
lps[0] = 0;
int j = 0;
for(int i =1;i<str.length;i++){
if(str[j] == str[i]){
lps[i] = j+1;
j++;
i++;
}else{
if(j!=0){
j = lps[j-1];
}else{
lps[i] = j+1;
i++;
}
}
}
return lps;
}
public boolean patternExistKMP(char[] text,char[] pat){
int[] lps = computeLPS(pat);
int i=0,j=0;
while(i<text.length && j<pat.length){
if(text[i] == pat[j]){
i++;
j++;
}else{
if(j!=0){
j = lps[j-1];
}else{
i++;
}
}
}
if(j==pat.length)
return true;
return false;
}
}