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

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 Hash-Werte ü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

<?php

function rabinKarp($pattern, $text)
{
   $d = 256; // Number of characters in the input alphabet
   $q = 101; // A prime number

   $M = strlen($pattern);
   $N = strlen($text);
   $p = 0; // Hash value for pattern
   $t = 0; // Hash value for text
   $h = 1;

   // Calculate the hash value of pattern and first window of text
   for ($i = 0; $i < $M - 1; $i++)
      $h = ($h * $d) % $q;

   for ($i = 0; $i < $M; $i++) {
      $p = ($d * $p + ord($pattern[$i])) % $q;
      $t = ($d * $t + ord($text[$i])) % $q;
   }

   // Slide the pattern over text one by one
   for ($i = 0; $i <= $N - $M; $i++) {

      // Check the hash values of current window of text and pattern
      // If the hash values match, then only check for characters one by one
      if ($p == $t) {
         $match = true;

         // Check for characters one by one
         for ($j = 0; $j < $M; $j++) {
            if ($text[$i + $j] != $pattern[$j]) {
               $match = false;
               break;
            }
         }

         // Pattern found
         if ($match)
            echo "Pattern found at index " . $i . "<br>";
      }

      // Calculate the hash value for the next window of text
      if ($i < $N - $M) {
         $t = ($d * ($t - ord($text[$i]) * $h) + ord($text[$i + $M])) % $q;

         // If the calculated hash value is negative, make it positive
         if ($t < 0)
            $t = $t + $q;
      }
   }
}

// Example usage
$text = "ABCABCABCABCABC";
$pattern = "BC";
rabinKarp($pattern, $text);
?>

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

Erklärung 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.

Fazit

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 passenden Hash-Berechnungen demonstriert das Programm die Funktionalität und Nützlichkeit des Rabin-Karp-Algorithmus für die Mustersuche in PHP.

Das obige ist der detaillierte Inhalt vonPHP-Programm für den Rabin-Karp-Algorithmus zur Mustersuche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!