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

  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. @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.

Kommentar verfassen