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 Zeichen neu berechnen, bringt gar nichts.
Sie muss sich durch Herausnahme des letzten und Hinzufügen der nächsten Zeichens in berechnen lassen,
z.B. die Quersumme modulo .
Dann ist die gesamte Komplexität im Average Case , jedoch im Worst Case ,
wenn das Muster auf jede Textstelle passt.