Ich bin daran interessiert, den Rabin-Karp-Algorithmus zu implementieren, um nach Unterzeichenfolgen zu suchen, wie im Wiki angegeben: Ссылка . Nicht für Hausaufgaben, aber für Eigeninteresse. Ich habe den Rabin-Karp-Algorithmus implementiert (siehe unten) und es funktioniert. Allerdings ist die Leistung wirklich sehr schlecht !!! Ich verstehe, dass meine Hash-Funktion grundlegend ist. Es scheint jedoch, dass ein einfacher Aufruf von strstr () immer meine Funktion rabin_karp () übertreffen wird. Ich kann verstehen, warum - die Hash-Funktion macht mehr Arbeit als eine einfache char-by-char jede Schleife zu vergleichen. Was fehlt mir hier? Sollte der Rabin-Karp-Algorithmus schneller sein als ein Aufruf von strstr ()? Wann wird der Rabin-Karp-Algorithmus am besten verwendet? Daher mein Eigeninteresse. Habe ich den Algorithmus sogar richtig implementiert?
%Vor%Sie haben den Hash nicht korrekt implementiert. Der Schlüssel zu Rabin-Karp ist es, inkrementell den Hash zu aktualisieren, wenn sich die potenzielle Übereinstimmung entlang der zu durchsuchenden Zeichenfolge bewegt. Wie Sie festgestellt haben, wenn Sie den gesamten Hash für jede mögliche Match-Position neu berechnen, werden die Dinge wirklich langsam.
Für jeden Fall außer dem ersten Vergleich sollte Ihre Hash-Funktion einen vorhandenen Hash, ein neues Zeichen und ein altes Zeichen verwenden und einen aktualisierten Hash zurückgeben.
Rabin-Karp ist ein rollender Hash-Algorithmus - die Idee besteht darin, den Teilstring um eine Position in eine Richtung (links oder rechts) zu bewegen und den Hash mit einer konstanten Anzahl von Operationen neu berechnen zu können. Wie Sie es implementiert haben, hat die Suche die Komplexität O (N * L), wobei N die Länge der großen Zeichenfolge und L die Länge der Zeichenfolge ist, nach der Sie suchen. Dies ist die Komplexität der naivsten Herangehensweise und ist meiner Meinung nach eine kleine Belästigung.
Um Ihren Algorithmus zu verbessern, rechnen Sie die Exponenten von magic_exp vor und verwenden Sie sie, um Ihren Hash zu "rollen" - im Grunde wie bei Polynomen müssen Sie den höchsten Grad multiplizieren mit magic_exp und den Hash des Symbols rechts hinzufügen (zum Verschieben) der Hash rechts).
Hoffe, das hilft.
strstr verwendet den KMP -Algorithmus, der auch dies ist linear in der Natur. Dies bedeutet, dass die Komplexität der beiden Algorithmen annähernd gleich ist. Von nun an ist die Konstante der wichtige Faktor. Besonders in dem Fall, dass Sie schlechte Hash-Funktionen mit vielen Kollisionen haben, wird der KMP viel schneller sein.
BEARBEITEN : Noch eine Sache. Für den Rabin-Karp-Algorithmus ist es sehr wichtig, dass alle Hash-Codes der Präfixe vorberechnet werden. Jetzt implementierst du nicht richtiges Rabin Karp, weil die Aufrufe deiner Funktion linear sind, nicht konstant in der Komplexität. (Was übrigens bedeutet, dass Wikipedia keine gute Quelle ist, um Rabin Karp zu lernen).
Tags und Links algorithm string c++ performance rabin-karp