PHP 使用Rabin-Karp算法进行模式搜索

什么是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 alphabetq = 101; // A prime number

   M = strlen(pattern);
   N = strlen(text);
   p = 0; // Hash value for patternt = 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 . "  
";
      }

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

输出

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中进行模式搜索的功能和实用性。