数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学用于模式搜索的 Rabin-Karp 算法的 PHP 程序
什么是 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 . "
";
}
// 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 中进行模式搜索的功能和实用性。
更新于：2023年8月1日
浏览量：133
广告