什么是 Rabin-Karp 算法？

Rabin-Karp 算法是一种字符串模式匹配算法，可以有效地搜索较大文本中模式的出现情况。它由 Michael O. Rabin 和 Richard M. Karp 于 1987 年开发。

该算法利用散列技术来比较模式和文本子字符串的散列值。其工作原理如下：

• 计算模式和文本的第一个窗口的哈希值。

• 将模式滑过文本，每次一个位置并比较哈希值。

• 如果哈希值匹配，则比较模式的字符和文本的当前窗口以确认匹配。

• 如果有匹配，记录匹配的位置/索引。

• 使用滚动哈希函数计算文本的下一个窗口的哈希值。

• 重复步骤 3 至 5，直到检查完文本的所有位置。

滚动哈希函数通过减去前一个窗口中第一个字符的贡献并添加新窗口中下一个字符的贡献来有效地更新每个新窗口的哈希值。这有助于避免为每个窗口从头开始重新计算哈希值，从而使算法更加高效。

用于模式搜索的 Rabin-Karp 算法的 PHP 程序

<?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>";
      }

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

输出

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

代码说明

PHP 代码实现了用于模式搜索的 Rabin-Karp 算法。它将模式和文本作为输入，并搜索文本中模式的出现。该算法计算模式和文本的第一个窗口的哈希值。然后，它将模式滑过文本，比较当前窗口和模式的哈希值。如果哈希值匹配，则进一步一一验证字符。如果找到匹配项，它将打印找到该模式的索引。该算法使用滚动哈希函数来有效地更新每个窗口的哈希值。该代码通过在文本“ABCABCABCABCABC”中搜索模式“BC”来演示该算法的用法。

结论

总之，PHP 程序有效地实现了用于模式搜索的 Rabin-Karp 算法。通过利用滚动哈希函数并比较哈希值，该算法可以有效地搜索较大文本中模式的出现。该程序正确识别文本中找到模式的索引并输出结果。该程序具有清晰的结构和适当的哈希计算，演示了 Rabin-Karp 算法在 PHP 中进行模式搜索的功能和实用性。