Program PHP untuk carian corak menggunakan algoritma Rabin-Karp

Apakah algoritma Rabin-Karp?

Algoritma Rabin-Karp ialah algoritma pemadanan corak rentetan yang cekap mencari kejadian corak dalam teks yang lebih besar. Ia dibangunkan pada tahun 1987 oleh Michael O. Rabin dan Richard M. Karp.

Algoritma ini menggunakan teknik pencincangan untuk membandingkan nilai pencincangan corak dan subrentetan teks. Begini cara ia berfungsi:

• Kira nilai cincang bagi tetingkap pertama corak dan teks.

• Luncurkan corak ke atas teks, satu kedudukan pada satu masa dan bandingkan cincang.

• Jika cincang sepadan, bandingkan aksara corak dan tetingkap semasa teks untuk mengesahkan padanan.

• Jika ada perlawanan, catat kedudukan/indeks yang sepadan.

• Kira cincang tetingkap teks seterusnya menggunakan fungsi cincang bergolek.

• Ulang langkah 3 hingga 5 sehingga semua kedudukan teks telah disemak.

Fungsi cincang bergulir mengemas kini nilai cincang secara berkesan untuk setiap tetingkap baharu dengan menolak sumbangan aksara pertama dalam tetingkap sebelumnya dan menambah sumbangan aksara seterusnya dalam tetingkap baharu. Ini membantu mengelakkan pengiraan semula cincang dari awal untuk setiap tetingkap, menjadikan algoritma lebih cekap.

Program PHP untuk algoritma Rabin-Karp untuk carian corak

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

Output

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

Perihalan kod

Kod PHP melaksanakan algoritma Rabin-Karp untuk carian corak. Ia memerlukan corak dan teks sebagai input dan mencari teks untuk kemunculan corak. Algoritma ini mengira nilai cincang bagi tetingkap pertama corak dan teks. Ia kemudian meluncurkan corak ke atas teks, membandingkan cincang tetingkap semasa dan corak. Jika cincang sepadan, aksara akan disahkan lagi satu demi satu. Jika padanan ditemui, ia mencetak indeks di mana corak ditemui. Algoritma menggunakan fungsi cincang bergulir untuk mengemas kini nilai cincang dengan cekap untuk setiap tetingkap. Kod ini menunjukkan penggunaan algoritma dengan mencari corak "BC" dalam teks "ABCABCABCABCABC".

Kesimpulan

Ringkasnya, program PHP melaksanakan algoritma Rabin-Karp dengan berkesan untuk carian corak. Dengan menggunakan fungsi cincang bergolek dan membandingkan nilai cincang, algoritma boleh mencari kejadian corak dalam teks yang lebih besar dengan cekap. Atur cara dengan betul mengenal pasti indeks corak yang ditemui dalam teks dan mengeluarkan hasilnya. Dengan struktur yang jelas dan pengiraan cincang yang sesuai, program ini menunjukkan kuasa dan kegunaan algoritma Rabin-Karp untuk carian corak dalam PHP.

Atas ialah kandungan terperinci Program PHP untuk carian corak menggunakan algoritma Rabin-Karp. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!