Program PHP untuk Algoritma Rabin-Karp untuk Carian Corak

Apakah itu Algoritma Rabin-Karp?

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

Algoritma menggunakan teknik pencincangan untuk membandingkan nilai cincangan corak dan subrentetan teks. Ia berfungsi seperti berikut:

• Kira nilai cincang corak dan tetingkap pertama teks.

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

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

• Jika ada perlawanan, catat kedudukan/indeks perlawanan.

• Kira nilai cincang untuk tetingkap seterusnya teks menggunakan fungsi cincang bergolek.

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

Fungsi cincang bergulir mengemas kini nilai cincang untuk setiap tetingkap baharu dengan cekap dengan menolak sumbangan aksara pertama dalam tetingkap sebelumnya dan menambah sumbangan aksara seterusnya dalam tetingkap baharu. Ini membantu mengelakkan pengiraan semula nilai 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 . "<br>";
      }

      // 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

Penjelasan kod

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

Kesimpulan

Kesimpulannya, program PHP melaksanakan algoritma Rabin-Karp dengan berkesan untuk pencarian corak. Dengan menggunakan fungsi cincang bergulir dan membandingkan nilai cincang, algoritma secara cekap mencari kejadian corak dalam teks yang lebih besar. Program ini dengan betul mengenal pasti indeks di mana corak ditemui dalam teks dan mengeluarkan hasilnya. Dengan struktur yang jelas dan pengiraan cincang yang sesuai, program ini menunjukkan kefungsian dan kegunaan algoritma Rabin-Karp untuk carian corak dalam PHP.

Atas ialah kandungan terperinci Program PHP untuk Algoritma Rabin-Karp untuk Carian Corak. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!