用于模式搜索的 Rabin-Karp 算法的 PHP 程序
phpserver side programmingprogramming更新于 2025/8/29 9:22:17
什么是 Rabin-Karp 算法?
Rabin-Karp 算法是一种字符串模式匹配算法，可以有效地在较长的文本中搜索某个模式的出现。该算法由 Michael O. Rabin 和 Richard M. Karp 于 1987 年开发。
该算法利用哈希技术比较模式和文本子字符串的哈希值。其工作原理如下:
计算模式和文本第一个窗口的哈希值。
将模式逐个滑动到文本上，并比较哈希值。
如果哈希值匹配，则比较模式的字符和文本的当前窗口以确认匹配。
如果匹配，则记录匹配的位置/索引。
使用滚动哈希函数计算文本下一个窗口的哈希值。
重复步骤 3 至 5，直到检查完文本的所有位置。
滚动哈希函数通过减去前一个窗口中第一个字符的贡献并添加新窗口中下一个字符的贡献来有效地更新每个新窗口的哈希值。这有助于避免为每个窗口重新计算哈希值，从而提高算法的效率。
用于模式搜索的 Rabin-Karp 算法的 PHP 程序
<?php
function rabinKarp($pattern, $text)
{
$d = 256; // 输入字母表中的字符数
$q = 101; // 一个素数
$M = strlen($pattern);
$N = strlen($text);
$p = 0; // 模式的哈希值
$t = 0; // 文本的哈希值
$h = 1;
// 计算模式和文本第一个窗口的哈希值
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;
}
// 将图案逐一滑到文本上
for ($i = 0; $i <= $N - $M; $i++) {
// 检查当前窗口的文本和图案的哈希值
// 如果哈希值匹配，则只需逐个检查字符
if ($p == $t) {
$match = true;
// 逐个检查字符
for ($j = 0; $j < $M; $j++) {
if ($text[$i + $j] != $pattern[$j]) {
$match = false;
break;
}
}
// 找到模式
if ($match)
echo "Pattern found at index " . $i . "
";
}
// 计算下一个文本窗口的哈希值
if ($i < $N - $M) {
$t = ($d * ($t - ord($text[$i]) * $h) + ord($text[$i + $M])) % $q;
// 如果计算出的哈希值为负数，则将其设为正数
if ($t < 0)
$t = $t + $q;
}
}
}
// 示例用法
$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 中模式搜索的功能和实用性。
