next up previous contents
Nächste Seite: Endliche Automaten Aufwärts: String Matching Vorherige Seite: String Matching   Inhalt

Rabin-Karp-Algorithmus

Algorithmus:
Der Rabin-Karp-Algorithmus berechnet an jeder Textposition eine Hashfunktion und vergleicht sie mit der Hashfunktion des Musters. Bei Übereinstimmung wird zusätzlich der Text mit dem String des Musters verglichen, da die Hashfunktion üblicherweise nicht eindeutig ist.

Komplexität:
Die Hashfunktion an jeder Stelle aus $ m$ Zeichen neu berechnen, bringt gar nichts. Sie muss sich durch Herausnahme des letzten und Hinzufügen der nächsten Zeichens in $ O(1)$ berechnen lassen, z.B. die Quersumme modulo $ p$. Dann ist die gesamte Komplexität im Average Case $ O(n+m)$, jedoch im Worst Case $ O(nm)$, wenn das Muster auf jede Textstelle passt.



2003-10-08