Der Karp-Rabin Algorithmus ist ein effizienter Suchalgorithmus zur Mustererkennung in Texten, der auf der Verwendung von Hash-Funktionen basiert. Er ermöglicht es, ein Muster in einem Text mit einer durchschnittlichen Zeitkomplexität von , wobei die Länge des Textes ist, zu finden. Der Algorithmus berechnet einen Hash-Wert für das Muster und für die substrings des Textes mit der gleichen Länge wie das Muster. Wenn die Hash-Werte übereinstimmen, wird eine genauere Überprüfung des Musters durchgeführt, um sicherzustellen, dass es sich tatsächlich um einen Treffer handelt.
Die Hash-Funktion wird typischerweise als polynomialer Hash definiert:
wobei die Zeichen des Musters, die Länge des Musters, eine Basis und eine Primzahl ist. Ein Vorteil des Karp-Rabin Algorithmus ist die Möglichkeit, den Hash-Wert effizient von einem substring zum nächsten zu aktualisieren, was die Berechnungen beschleunigt.
Starte dein personalisiertes Lernelebnis mit acemate. Melde dich kostenlos an und finde Zusammenfassungen und Altklausuren für deine Universität.