algorithm
Knuth Morris Pratt (KMP) Algorithmus
Suche…
Einführung
Der KMP ist ein Musterabgleichungsalgorithmus, der nach Vorkommen eines "Wortes" W innerhalb einer Haupt- "Textzeichenfolge" S sucht, indem er die Beobachtung verwendet, dass, wenn eine Nichtübereinstimmung auftritt, wir über ausreichende Informationen verfügen, um zu bestimmen, wo die nächste Übereinstimmung beginnen könnte Nutzen Sie diese Informationen, um zu vermeiden, dass die Zeichen, von denen wir wissen, dass sie auf jeden Fall übereinstimmen, übereinstimmen. Die Komplexität der Suche nach einem Muster reduziert sich auf 0 (n) .
KMP-Beispiel
Algorithmus
Dieser Algorithmus ist ein zweistufiger Prozess. Zuerst erstellen wir ein Hilfsarray lps [] und verwenden dieses Array dann zum Durchsuchen des Musters.
Vorverarbeitung :
- Wir bereiten das Muster vor und erstellen ein Hilfsarray lps [], das zum Überspringen von Zeichen während des Abgleichs verwendet wird.
- Hier gibt lps [] das längste richtige Präfix an, das auch ein Suffix ist. Ein richtiges Präfix ist ein Präfix, in dem kein ganzer String enthalten ist. Zum Beispiel sind Präfixe des Strings ABC "" , "A" , "AB" und "ABC" . Richtige Präfixe sind “” , “A” und “AB” . Suffixe der Zeichenfolge sind "" , "C" , "BC" und "ABC" .
Suchen
Wir stimmen mit den Zeichen txt [i] und pat [j] überein und erhöhen i und j, während pat [j] und txt [i] weiterhin übereinstimmen.
Wenn wir eine Nichtübereinstimmung sehen, wissen wir, dass die Zeichen pat [0..j-1] mit txt [i-j + 1… i-1] übereinstimmen. Wir wissen auch, dass lps [j-1] die Anzahl der Zeichen von pat ist [0… j-1] , die sowohl das richtige Präfix als auch das Suffix sind. Daraus können wir schließen, dass wir diese lps [j-1] -Zeichen nicht mit txt [ij… i-1] abgleichen müssen, da wir wissen, dass diese Zeichen bekannt sind wird trotzdem passen.
Implementierung 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;
}
}