Wie der naive Algorithmus beginnt der Knuth-Morris-Pratt-Algorithmus am Textanfang und arbeitet sich anschließend durch den Text durch. Wird ein gleichlautendes Präfix gefunden, zeigt sich im naiven Algorithmus allerdings, dass alle bisher gefundenen Zeichen umsonst verglichen wurden. Knuth-Morris-Pratt hingegen untersucht zunächst das Suchmuster auf sich wiederholende Präfixe.

So wiederholt sich im Wort 'ananas' das Präfix 'ana' ab der 3. Position: 'ananas'. Wird nun im Text anananas verglichen, so findet man im naive Algorithmus anananas und stellt dann fest, dass das ein 'n' statt des gesuchten 's' gefunden wurde.

Nun haben wir jedoch zuvor nach sich wiederholenden Präfixen gesucht und festgestellt, dass sich im Bereich anana das (dreistellige) Prefix 'ana' ab der 3. Stelle wiederholt. Das bedeutet, dass wir an der 6. Stelle, wo wir das 'n' statt des gesuchten 's' gefunden haben, bereits die Stellen 3, 4 und 5 als Präfix erkannt haben. In dem Fall sind wir im Suchmuster nicht an Stelle 6 (das 's'), sondern an Stelle 4 (das 'n').

Die grundlegende ist folgende: Wörter können Präfixe haben. So begibt es sich, dass das Verb 'begeben' eine Buchstabenkombination 'be' hat, die sich im Wort wiederholt: begeben. Findet sich im Text nun eine Buchstabenkombination 'begebegeben', so finden wir begebeg und stellen bei dem zweiten 'g' fest, dass wir nicht das gesucht Wort 'begeben' gefunden haben. Aber der letzte Treffer entsprach Präfix 'be'. Da wir die nachfolgenden Buchstaben noch nicht geprüft haben, könnte es sein, dass wir grade erfolgreich die ersten beiden Buchstaben des Suchwortes 'begeben' gefunden zu haben, leider vergleichen wir nicht mit dem ersten 'be' im Suchwort (begeben), sondern mit dem zweiten 'be' im Suchwort (begeben). Im naive Algorithmus müssten wir jetzt an das 'e' zurückgekehren ('begebegeben') und dort die Suche erneut starten, obwohl wir bis zum roten gekennzeichneten 'b' den Text bereits analysiert haben. Der Text zwischen 'e' und 'b' müsste erneut analysiert werden.

Hier können wir optimieren. Wenn wir noch wüssten, dass wir soeben 'be' gelesen hätten, also die ersten beiden Buchstaben des Wortes, dann bräuchten wir nicht im Text zurückzuspringen, sondern wir würden das Suchwort einfach ab dem 3. Buchstaben weiter vergleichen. Um das bewerkstelligen müssen wir das Suchpattern daraufhin untersuchen, an welcher Stelle das Suchmuster dem Anfang des Suchmusters entspricht. Wir legen neben dem Suchmuster eine Tabelle an, die für jeden Buchstaben sagt, an welcher Stelle der nächste Vergleich im Suchmuster stattfinden muss, um einen gültigen Vergleich zu erzeugen.

Stellen wir also nach einem Präfix fest, dass das Wort nicht passt, schauen wir in der Tabelle nach, mit welcher vorherigen Stelle im Suchmuster wir vergleichen können, um eventuell doch noch ein Element zu finden.

Wir suchen das Suchmuster „ananas“ im Text „anabellmagananasananabolika.“ (Anabell mag Ananas an Anabolika).

Statt eines einfachen Suchmusters, müssen wir aus dem Pattern nun eine Reihe von Informationen erzeugen. Damit wir hier nicht mit tausenden Argumenten jonglieren müssen, packen wir zunächst alles, was zum Suchmuster gehört in eine eigene kleine Struktur:

struct Pattern
{
    char const   * Pattern;
    unsigned int   Length;
    int          * Table;
};

Hier können wir die Tabelle speichern, die die Verschiebung im Suchmuster speichert und uns die Länge des Suchmusters merken, so dass wir die sie nicht laufend neu ermitteln müssen.

Wir erzeugen nun ein Suchmuster, indem wir eine Pattern-Struktur anlegen und die Adresse des Suchmusters in die Struktur schreiben:

struct Pattern pat;
pat.Pattern = "ababcabab";

Anschließend müssen wir irgendwie die Tabelle erzeugen. Das funktioniert wie folgt: wir lassen den ersten Buchstaben weg, da der erste Buchstabe keine Wiederholung eines vorherigen Buchstabens sein kann. Wir interessieren uns für Präfixwiederholungen ab dem 2. Buchstaben. An jeder Position des Suchmusters interessiert uns, wie viele Stellen der vorhergehenden Buchstaben dem Wortanfang entsprechen.

Schauen wir uns die Tabelle einmal für 'ananas' an:

char createPrefixTable( struct Pattern * pattern )
{
    int patternPos;       // Position im Pattern
    int partLength;       // Länge der Übereinstimmung
 
    pattern->Length = strlen( pattern->Pattern );
 
    pattern->Table = malloc( ( 1 + pattern->Length ) * sizeof( int ) );
    if( pattern->Table )
    {
        patternPos = 0;
        partLength = -1;
 
        pattern->Table[ 0 ] = -1;
 
        while( patternPos < pattern->Length )
        {
            while( partLength >= 0 && pattern->Pattern[ partLength ] != pattern->Pattern[ patternPos ] )
                partLength = pattern->Table[ partLength ];
 
            patternPos++;
            partLength++;
            pattern->Table[ patternPos ] = partLength;
        }
 
        return TRUE;
    }
 
    return FALSE;
}

Die Suche selbst ist nun vergleichsweise einfach: Man geht den Text durch und vergleicht wie in der naive Algorithmus Suche. Je größer das Alphabet (also je kleiner die Chance auf ein Präfix zu stoßen) desto eher wird sich der Knuth-Morris-Pratt-Algorithmus auch ähnlich der naive Algorithmus Suche verhalten. Bricht er jedoch in einem Teil des Suchmusters ab, weil Text und Suchmuster nicht mehr übereinstimmt, so kann er ein bereits gefundenes Präfix überspringen.

Beim Lesen des Quelltextes ist es hilfreich, sich vor Augen zu führen, wie der Regelfall abläuft. Der Regelfall ist wie im naive Algorithmus dass der erste Buchstabe bereits nicht übereinstimmt. In dem Fall ist patternPos == 0, es wird also mit dem 1. Buchstaben (Index 0 im Suchmuster) verglichen. Wenn er nicht übereinstimmt, wird patternPos auf den Wert der Tabelle an Index von patternPos (also immer noch 0) gesetzt. Der Wert ist der Spezialfall in der Tabelle: -1.

Anschließend wird patternPos ebenso wie textPos um 1 erhöht, so dass patternPos wieder 0 ist und anschließend der nächste Buchstabe im Text mit dem Buchstaben des Suchmusters an Index 0 verglichen wird. Das entspricht dem naiven Algorithmus.

int find( char const * text, unsigned int textLength, struct Pattern * pattern )
{
    int textPos = 0;
    int patternPos = 0;
 
    while( textPos < textLength )
    {
        while( patternPos >= 0 && text[ textPos ] != pattern->Pattern[ patternPos ] )
            patternPos = pattern->Table[ patternPos ];
 
        patternPos++;
        textPos++;
 
        if( patternPos == pattern->Length )
            return textPos - pattern->Length;
    }
 
    return -1;
}

• Wikipedia: Knuth-Morris-Pratt-Algorithmus

• Beispielquelltext: knuthmorrispratt.c