PHP-Programm zur Mustersuche mit dem Rabin-Karp-Algorithmus

Was ist der Rabin-Karp-Algorithmus?

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

Dieser Algorithmus nutzt Hashing-Techniken, um Hash-Werte von Mustern und Textteilzeichenfolgen zu vergleichen. So funktioniert es:

• Berechnen Sie den Hashwert des ersten Muster- und Textfensters.

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

• Wenn die Hashes übereinstimmen, vergleichen Sie die Zeichen des Musters und des aktuellen Textfensters, um die Übereinstimmung zu bestätigen.

• Wenn es eine Übereinstimmung gibt, notieren Sie die übereinstimmende Position/Index.

• Berechnen Sie den Hash des nächsten Textfensters 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 effektiv 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 Hashes für jedes Fenster von Grund auf neu berechnet werden müssen, 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 . "</p><p>";
      }

      // 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

Codebeschreibung

PHP-Code implementiert den Rabin-Karp-Algorithmus für die Mustersuche. Es nimmt ein Muster und einen Text als Eingabe und durchsucht den Text nach Vorkommen des Musters. Dieser Algorithmus berechnet den Hashwert des ersten Fensters aus Muster und Text. Anschließend wird das Muster über den Text geschoben und der Hash des aktuellen Fensters mit dem Muster verglichen. Wenn die Hashes übereinstimmen, werden die Zeichen einzeln weiter überprüft. Wenn eine Übereinstimmung gefunden wird, wird der Index gedruckt, an dem das Muster gefunden wurde. Der Algorithmus verwendet eine rollierende Hash-Funktion, um den Hash-Wert für jedes Fenster effizient zu aktualisieren. Dieser 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 für die Mustersuche effektiv implementiert. Durch die Nutzung einer rollierenden Hash-Funktion und den Vergleich der Hash-Werte kann der Algorithmus effizient nach Vorkommen von Mustern in größeren Texten suchen. Das Programm identifiziert den Index des gefundenen Musters im Text korrekt und gibt das Ergebnis aus. Mit einer klaren Struktur und geeigneten Hash-Berechnungen demonstriert dieses Programm die Leistungsfähigkeit und Nützlichkeit des Rabin-Karp-Algorithmus für die Mustersuche in PHP.

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