Der Nachteil unseres Brute-Force-Algorithmus vom Kapitel zuvor ist der, dass dieser stur Zeichen für Zeichen, Position um Position vergleicht. Knuth, Morris und Pratt haben diesen Algorithmus verbessert (verfeinert).

Sie hatten die Idee die Fehlvergleiche (man spricht dabei von Mismatch) in den weiteren Algorithmus Miteinzubetziehen. Wir zum Beispiel ein Fehler an Position j gefunden, so gilt folgende Berechnung......

suchmuster[1...j-1] = text[i...i+j-2]  

Wollen wir uns das Prinzip mal bildlich ansehen.........

a

b

c

c

a

b

c

d

a

a

b

c

d

a

1.

a

b

c

d

2.

a

b

c

d

3.

a

b

c

d

4.

a

b

c

d

5.

a

b

c

d

Anhand dieser Tabelle lässt es sich prima erkenne, dass der nächste Suchvergleich immer zur Position springt, wo sich ein Fehlvergleich (Mismatch) ereignet hat oder im Falle eine übereinstimmenden Musters dahinter. Somit ist es mit diesem Algorithmus möglich, das Suchmuster um eine größere Distanz zu verschieben.

Für den Algorithmus ist auch eine Vorlaufphase (Preprocessing) nötig, bei dem Informationen des Suchmusters in einem Array der Länge m gespeichert werden. Hierzu benötigen wir eine weitere Funktion, die die uns diese berechnet.

Die Tabelle next verwenden wir, um die nächste Position für unseren Algorithmus KPM zu ermitteln. Eine genaue Erläuterung finden sie dazu auf dieser Webseiten.....

www.iti.fh-flensburg.de/lang/algorithmen/pattern/kmp.htm  

Hierzu nun unser Algorithmus dazu....

/*Download:kmp.c*/ #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 4096 char next[MAX]; /* i = Postion im Text */ /* j = Postion im Muster */ void kmpSearch(char *muster, char *text) { int i=0, j=0; int m=strlen(muster); /*Länge Muster*/ int n=strlen(text); /*Länge Text*/ init_next(muster); /* Tabelle für next berechnen*/ while (i<n) /*Solange wir nicht am Ende vom Text sind*/ { while (j>=0 && text[i]!=muster[j]) j=next[j]; i++; j++; if (j==m) { printf("Gefunden an Pos. %d\n",i-j); j=next[j]; } } } void init_next(char *muster) { int i, j, m=strlen(muster); next[0]=-1; for(i=0, j=-1; i<m; i++, j++, next[i]=j) while((j >=0) && (muster[i] != muster[j])) j=next[j]; } int main() { kmpSearch("ex", "a example text"); return 0; }

Weiterführende Links:

Knuth Morris Pratt :

http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/kmp.htm

http://www-igm.univ-mlv.fr/~lecroq/string/node8.html#SECTION0080

http://ivs.cs.uni-magdeburg.de/~dumke/EAD/Skript44.html