Bei der brute force-Methode muß man beim Auftreten eines Unterschieds wie eben beschrieben die Suche ein Zeichen hinter dem letzten Startpunkt im Text fortsetzen, weil man sonst möglicherweise ein Vorkommen des Musters übersieht.
Das ist bedauerlich, weil dadurch viele Zeichen aus text mehrfach betrachtet werden müssen.
Je nach Aufbau des Musters kann man allerdings auch weiter springen, bevor man mit erneutem Vergleichen beginnt, und spart sich dadurch einen Teil der Vergleiche.
Beispiel: falls das Muster folgenden Inhalt hat:
muster | [0] | [1] | [2] | [3] | [4] | |||||
a | b | b | b | c |
Ist dagegen das Muster:
muster | [0] | [1] | [2] | [3] | [4] | [5] | ||||
a | b | c | a | b | b |
Anstatt also die Suche jeweils beim Zeichen hinter dem letzten Start neu aufzusetzen, dürfte man unter Umständen auch gleich etwas weiter springen; wie weit hängt erstens vom Muster ab, und zweitens von der erreichten Position im Muster bis zum letzten Abbruch.
Diese Erkenntnis führt zu dem Verfahren von Knuth, Morris und Pratt.
Hier wird vor der eigentlichen Suche ein zusätzliches Feld geschaffen, anhand dessen zu jeder möglichen Abbruchposition eine erlaubte Sprungweite hinterlegt wird. Dieses Feld wird für jede Suche aufgrund des Musters einmal bestimmt; bei längeren Texten geht diese Vorabberechnung also nicht in die Laufzeit mit ein.
An jeder Position ist angegeben, wie viele Elemente vor dem aktuellen mit dem Stringanfang übereinstimmen (abgesehen davon, daß die unterste Sprungweite immer mit -1 eingetragen wird).
/* Time-stamp: "20.06.02 17:39 demo.c klaus@lap2.wachtler.de" * */ #include <stdlib.h> #include <stddef.h> #include <stdio.h> #include <string.h> /* liefert einen Index zurück, der die relative Position * von muster in text angibt (falls Muster in text enthalten ist); * sonst -1. * Die Länge von text ist n; die Länge von muster ist m. */ void init_sprweite( char muster[], int sprweite[], int m ) { int i, j; sprweite[0] = -1; for( (i=0), (j=-1); i<m; i++, j++, sprweite[i]=j) { while( (j>=0) && (muster[i]!=muster[j]) ) { j = sprweite[j]; } } } int sucheteilfeld_kmp( char text[], int n, char muster[], int sprweite[], int m ) { int index_text, index_muster; init_sprweite( muster, sprweite, m ); for( (index_text=0), (index_muster=0); index_muster<m && index_text<n; index_text++, index_muster++ ) { while( index_muster>=0 && text[index_text]!=muster[index_muster] ) { index_muster = sprweite[index_muster]; } } if( index_muster==m ) { return index_text - m; } else { return -1; } } int main( int nargs, char **args ) { // char text[] = // { // 'e', 'h', 'n', 'e', ' ', // 'm', 'e', 'h', 'm', 'e', 'm', 'm', 'e', 'h', 'm', 'e', 'm', 'a', ' ', // 'm', 'u', 'h' // }; // // char muster[] = // { // 'm', 'e', 'h', 'm', 'e', 'm', 'm', 'e', 'h', 'm', 'e', 'm', 'a', ' ', ///* zugehörige Sprungweiten: */ ///* -1, 0, 0, 0, 1, 2, 1, 1, 2, 3, 4, 5, 6, 0, 0 */ // // }; // char text[] = // { // 'z', 'a', 'b', 'z', 'a', 'z', 'a', // }; // // char muster[] = // { // 'z', 'a', 'z', 'a', ///* zugehörige Sprungweiten: */ ///* -1, 0, 0, 1, 2 */ // // }; char text[] = { 'z', 'a', 'z', 'z', 'a', 'z', 'a', }; char muster[] = { 'z', 'a', 'z', 'a', /* zugehörige Sprungweiten: */ /* -1, 0, 0, 1, 2 */ }; const int laenge_text = sizeof(text)/sizeof(text[0]); const int laenge_muster = sizeof(muster)/sizeof(muster[0]); int sprweite[laenge_muster+1]; int position = sucheteilfeld_kmp( text, laenge_text, muster, sprweite, laenge_muster ); printf( "%d\n", position ); return 0; } /* main( int nargs, char **args ) */
www.wachtler.de