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.

Das hier fand ich gerade in den Untiefen meines Rechners. Als wir im letzten Semester Textsuchalgorithmen besprochen haben, hatte ich für meine Studis diese kleine Animation gebastelt, um zu zeigen, wie der Boyer-Moore Algorithmus mit Bad-Occurence-Heuristik funktioniert. Vielleicht nützt sie dem ein oder anderem auch etwas beim Verständnis. Um zum nächsten Schritt zu gelangen, einfach mit der Maus klicken ((Leider habe ich in OpenOffice keine Möglichkeit gefunden, einen Flashfilm so zu erzeugen, dass dieser automatisch abgespielt wird.))

Hier gibt’s das Flash-Filmchen nochmal in groß.