資料結構
網路
關係資料庫管理系統 (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
廣告