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

輸出

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 演算法。它將模式和文字作為輸入，並蒐索文本中模式的出現。該演算法計算模式和文字的第一個視窗的雜湊值。然後，它將模式滑過文本，比較當前視窗和模式的雜湊值。如果雜湊值匹配，則進一步一一驗證字元。如果找到匹配項，它將列印找到該模式的索引。該演算法使用滾動雜湊函數來有效地更新每個視窗的雜湊值。該程式碼透過在文字“ABCABCABCABCABCABC”中搜尋模式“BC”來演示該演算法的用法。

結論

總之，PHP 程式有效地實現了用於模式搜尋的 Rabin-Karp 演算法。透過利用滾動雜湊函數並比較雜湊值，該演算法可以有效地搜尋較大文字中模式的出現。該程式正確識別文本中找到模式的索引並輸出結果。該程式具有清晰的結構和適當的雜湊計算，演示了 Rabin-Karp 演算法在 PHP 中進行模式搜尋的功能和實用性。

以上是PHP程式用於Rabin-Karp演算法進行模式搜尋的詳細內容。更多資訊請關注PHP中文網其他相關文章！