Der Knuth-Morris-Pratt Algorithmus leicht erklärt

Ein weiterer Textsuchalgorithmus-Klassiker ist der Algorithmus der Herren Knuth ((ja, genau der)), Morris und Pratt. Auch dazu habe ich eine kleine Animation gebastelt und stelle sie hier — auch auf ganz besonderen Wunsch eines einzelnen Herren — zur Verfügung.

Flash-Film in groß

Und hier gibts noch ein nettes Video, in dem Mr. Knuth himself erklärt, wie er auf diesen Algorithmus gekommen ist.

5 Kommentare

Antworten →

  1. ich danke dir! 😉 …aber das Video mit „Mr Knuth himself“ werd ich wohl gekonnt ignorieren…soweit reicht mein interesse dann lange nich 😛
    …so und jetz dann bitte auch genau das in der Prüfung behandeln 😉

  2. Ja gerne. Na dann werd ich mal als Prüfungsfrage vorschlagen „Erläutern Sie, wie Donald Knuth auf den KMP-Algorithmus gekommen ist!“ 😛

  3. Wenn du das machst, zieh ich mir den größten Mist aller Zeiten aus den Fingern…wird dann ne lustige Kontrolle für euch 😛

  4. Tut mir leid, hier wieder die Petze zu machen:

    Die Fehlerfunktion ist falsch:
    In der while-Schleife sind bei Beginn i=j=0. Daher ist die erste if-Bedingung erfüllt. -> i+1=j+1. Damit ist auch im nächsten Durchlauf P[i]==P[j]

    Die Fehlerfunktion ist also immer:
    1,2,3,4,…,m

    Hier gibts eine ganz gute Beschreibung zur Prefix-Funktion:
    http://www.csc.liv.ac.uk/%7Emichele/TEACHING/COMP309/2005/Lec5.1.4.pdf

  5. @René: Danke für den Hinweis, das i muss natürlich mit 1 initialisiert werden. Danke für’s durchgucken, ich werd das morgen früh gleich ändern.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.