PHP program for pattern search using Rabin-Karp algorithm

What is the Rabin-Karp algorithm?

The Rabin-Karp algorithm is a string pattern matching algorithm that efficiently searches for occurrences of patterns in larger texts. It was developed in 1987 by Michael O. Rabin and Richard M. Karp.

This algorithm utilizes hashing technology to compare the hash value of a pattern and a text substring. Here's how it works:

• Calculate the hash value of the first window of pattern and text.

• Slide the pattern over the text, one position at a time and compare the hashes.

• If the hashes match, compare the characters of the pattern and the current window of text to confirm the match.

• If there is a match, record the matching position/index.

• Calculate the hash value of the next window of text using a rolling hash function.

• Repeat steps 3 to 5 until all positions of the text have been checked.

The rolling hash function effectively updates the hash value for each new window by subtracting the contribution of the first character in the previous window and adding the contribution of the next character in the new window. This helps avoid recalculating hashes from scratch for each window, making the algorithm more efficient.

PHP program for Rabin-Karp algorithm for pattern search

<?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);
?>

Output

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

Code description

PHP code implements the Rabin-Karp algorithm for pattern search. It takes a pattern and text as input and searches the text for occurrences of the pattern. This algorithm calculates the hash value of the first window of pattern and text. It then slides the pattern over the text, comparing the hash of the current window and the pattern. If the hashes match, the characters are further verified one by one. If a match is found, it prints the index at which the pattern was found. The algorithm uses a rolling hash function to efficiently update the hash value for each window. This code demonstrates the use of the algorithm by searching for the pattern "BC" in the text "ABCABCABCABCABC".

in conclusion

In summary, the PHP program effectively implements the Rabin-Karp algorithm for pattern search. By utilizing a rolling hash function and comparing hash values, the algorithm can efficiently search for occurrences of patterns in larger texts. The program correctly identifies the index of the found pattern in the text and outputs the result. With a clear structure and appropriate hash calculations, this program demonstrates the power and usefulness of the Rabin-Karp algorithm for pattern searching in PHP.

The above is the detailed content of PHP program for pattern search using Rabin-Karp algorithm. For more information, please follow other related articles on the PHP Chinese website!