Was ist der Rabin-Karp-Algorithmus?

Der Rabin-Karp-Algorithmus ist ein String-Pattern-Matching-Algorithmus, der effizient nach Vorkommen eines Musters in einem größeren Text sucht. Es wurde 1987 von Michael O. Rabin und Richard M. Karp entwickelt.

Der Algorithmus verwendet eine Hashing-Technik, um die Hashwerte des Musters und der Teilzeichenfolgen des Textes zu vergleichen. Es funktioniert wie folgt:

• Berechnen Sie den Hashwert des Musters und des ersten Fensters des Textes.

• Schieben Sie das Muster eine Position nach der anderen über den Text und vergleichen Sie die Hashwerte.

• Wenn die Hashwerte übereinstimmen, vergleichen Sie die Zeichen des Musters und das aktuelle Textfenster, um die Übereinstimmung zu bestätigen.

• Wenn es eine Übereinstimmung gibt, notieren Sie die Position/den Index der Übereinstimmung.

• Berechnen Sie den Hash-Wert für das nächste Fenster des Textes mithilfe einer rollierenden Hash-Funktion.

• Wiederholen Sie die Schritte 3 bis 5, bis alle Positionen des Textes überprüft wurden.

Die Rolling-Hash-Funktion aktualisiert effizient den Hash-Wert für jedes neue Fenster, indem sie den Beitrag des ersten Zeichens im vorherigen Fenster subtrahiert und den Beitrag des nächsten Zeichens im neuen Fenster hinzufügt. Dadurch wird vermieden, dass der Hash-Wert für jedes Fenster von Grund auf neu berechnet wird, wodurch der Algorithmus effizienter wird.

PHP-Programm für den Rabin-Karp-Algorithmus zur Mustersuche

";
      }

      // Calculate the hash value for the next window of text
      if ($i 

Ausgabe

Pattern found at index 1 
Pattern found at index 4
Pattern found at index 7
Pattern found at index 10
Pattern found at index 13

Erläuterung des Codes

Der PHP-Code implementiert den Rabin-Karp-Algorithmus zur Mustersuche. Es nimmt ein Muster und einen Text als Eingaben und sucht nach Vorkommen des Musters im Text. Der Algorithmus berechnet die Hashwerte für das Muster und das erste Fenster des Textes. Anschließend verschiebt es das Muster über den Text und vergleicht die Hashwerte des aktuellen Fensters und des Musters. Wenn die Hash-Werte übereinstimmen, werden die Zeichen einzeln weiter überprüft. Wenn eine Übereinstimmung gefunden wird, wird der Index gedruckt, in dem das Muster gefunden wird. Der Algorithmus verwendet eine rollierende Hash-Funktion, um den Hash-Wert für jedes Fenster effizient zu aktualisieren. Der Code demonstriert die Verwendung des Algorithmus, indem er im Text „ABCABCABCABCABCABC“ nach dem Muster „BC“ sucht.

Abschluss

Zusammenfassend lässt sich sagen, dass das PHP-Programm den Rabin-Karp-Algorithmus zur Mustersuche effektiv implementiert. Durch die Verwendung einer rollierenden Hash-Funktion und den Vergleich von Hash-Werten sucht der Algorithmus effizient nach Vorkommen eines Musters in einem größeren Text. Das Programm erkennt korrekt die Indizes, an denen sich das Muster im Text befindet, und gibt die Ergebnisse aus. Mit einer klaren Struktur und entsprechenden Hash-Berechnungen demonstriert das Programm die Funktionalität und Nützlichkeit des Rabin-Karp-Algorithmus für die Mustersuche in PHP.