"Grep" (get regular expression and print) ist ein - vor allem auf Unix-Systemen - weit verbreitetes Utility zur effizienten Suche von Zeichenketten in Texten. Auch andere Programme benötigen effiziente Suchalgorithmen. Man denke nur an Datenbanken, Suchmaschinen, Textverarbeitung etc.
Im Vortrag geht es nun um die prinzipielle Funktionsweise solcher Algorithmen. Konkret wird der sogenannte Boyer-Moore Algorithmus behandelt, der in der Regel eine subliniare Laufzeit hat (d.h. weniger Vergleiche als Zeichen im Text).
1.Das Problem: Effizientes Finden von Zeichenketten in Texten
1.1 Erster Ansatz: »naive« Methode
führt zu worst-case Laufzeit O(n x m)
1.2 Besserer Ansatz: Weitere Sprünge durch Wissen über den Aufbau des Suchmusters mittels Preprocessing
führt zu worst-case Laufzeit O(n + m)
2. Fundamentales Preprocessing: Z-boxes
2.1 Definition von »Z-box« 
2.2 Einfacher Suchalgorithmus mit Z-boxes und linearer Laufzeit
2.3 Analog dazu: die »N-boxes« 
3. Der Boyer-Moore Algorithmus 
:
3.1 »Right-to-left scan«
3.2 »(Extended) bad-character-rule« 
3.3 Preprocessing für die extended bad-character-rule
3.4 »(Strong) good-suffix-rule« 
3.5 Preprocessing für die strong good-suffix-rule
3.5.1 Berechnung von L´[ ] 
3.5.2 Berechnung von l´[ ] 
3.6 Zusammenfassung