Einleitung Suchen in Texten

Nun behandeln wir das Suchen in Texten. Das Problem ist das Suchen eines Teilwortes in einem langen anderen Wort. Dies ist eine typische Funktion der Textverarbeitung. Nun ist eine effiziente Lösung gesucht. Das Maß der Effizienz ist hierbei die Anzahl der Vergleiche zwischen den Buchstaben der Worte. Den Vergleich von Zeichenketten nennt man String-Matching und eine nicht übereinstimmende Position nennt man Mismatch.

Vorgegebene Daten

Worte als Array:

- text[] zu durchsuchender Text

- pat[] 'Pattern', gesuchtes Wort

Wortlängen:

- n Länge des zu durchsuchenden Textes

- m Länge des gesuchten Wortes

$\sum$ Alphabet, $\epsilon$ leerer String

Abstrakte Algorithmenbeschreibung:

Eingabe: text[], pat[]

Ausgabe: Index i mit text[i...i+m]=pat[1...m+1] oder -1 falls das gesuchte Wort nicht im Text vorkommt.

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5 zu finden.