next up previous contents
Nächste Seite: Rabin-Karp-Algorithmus Aufwärts: Ausgewählte Verfahren Vorherige Seite: Ausgewählte Verfahren   Inhalt

String Matching

Definition:
Beim String Matching wird ein Text der Länge $ n$ mit einem Muster (Pattern) der Länge $ m$ verglichen. Gesucht sind alle Positionen im Text, an denen das Muster vorkommt.

Primitiver Ansatz:
Vergleiche an jeder Position den Text mit dem Muster, bei einem Mismatch wird auf das nächste Eingabezeichen gesprungen, Worst Case Kosten $ O(nm)$.



Unterabschnitte

2003-10-08