http://update.proggen.org/ 2026-04-19T11:54:55+0200 http://update.proggen.org/ http://update.proggen.org/lib/tpl/proggenY/images/favicon.ico text/html 2022-09-22T19:39:26+0200 Anonymous (anonymous@undisclosed.example.com) http://update.proggen.org/doku.php?id=algo:stringmatching:boyer-moore&rev=1663868366 Boyer-Moore-Algorithmus Einleitung Der naive Algorithmus wie auch der Knuth-Morris-Pratt-Algorithmus setzen darauf erfolgreich ein Suchmuster zu finden. Das scheint sinnvoll, wenn das Alphabet klein ist und damit die Chance hoch ist, bei der Suche erfolg zu haben. Bei genauerer Betrachtung ist die Chance einen Treffer zu landen jedoch eher gering. Bei einem Unicode-Alphabet können 65336 Zeichen auftreten, die Chance das richtige zu finden ist also 1:65335. In einem text/html 2022-09-22T19:39:26+0200 Anonymous (anonymous@undisclosed.example.com) http://update.proggen.org/doku.php?id=algo:stringmatching:knuth-morris-pratt&rev=1663868366 Knuth-Morris-Pratt-Algorithmus Einleitung 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. text/html 2022-09-22T19:39:26+0200 Anonymous (anonymous@undisclosed.example.com) http://update.proggen.org/doku.php?id=algo:stringmatching:start&rev=1663868366 String-Matching * Knuth-Morris-Pratt - Präfix-Optimierung * Boyer-Moore - Überspringen von Bereichen, die das Pattern nicht enthalten können.