Texte durchsuchen - aber schnell (string-matching)

Computer speichern Texte zeichenweise ab. Will man ein Wort innerhalb eines Textes finden, so muss man Zeichen um Zeichen vergleichen. Fallen alle Vergleiche positiv aus, so kommt das gesuchte Wort an dieser Position vor.

Die obige Simulation zeigt den Boyer-Moore-Algorithmus. Die Leertaste verschiebt die Startposition des Suchwortes zur nächstmöglichen Position gemäss der am unteren Rand dargestellten Sprungtagelle. Zu Beginn wird für alle Zeichen die Länge des Suchwortes eingetragen. Anschliessend werden für alle Zeichen des Suchwortes die Position des ersten Vorkommens von rechts eingetragen. Dabei wird das Zeichen ganz rechts nicht in Betracht gezogen, da sonst eine Verschiebung um 0 resultieren würde. Damit ist für jedes Zeichen die optimale Sprunglänge festgelegt. Bei Abbruch der zeichenweisen Vergleiche kann aufgrund des nicht übereinstimmenden Buchstabens die korrekte Verschiebung ermittelt werden. Dieser Algorithmus ist in den meisten Fällen effizient.
Mit den Tasten 1 bis 8 können unterschiedliche Suchwörter ausgewählt werden.

FS IN - sci