Program C algoritma Rabin-Karp untuk carian corak

Padanan corak dalam C - Kita perlu mencari jika rentetan wujud dalam rentetan lain, sebagai contoh, rentetan "algoritma" wujud dalam rentetan "algoritma naif". Jika ia ditemui, maka lokasinya (iaitu di mana ia terletak) dipaparkan. Kami cenderung untuk mencipta fungsi yang mengambil tatasusunan 2 aksara dan mengembalikan kedudukan jika terdapat padanan Jika tidak, -1 dikembalikan.

Input: txt = "HERE IS A NICE CAP"
   pattern = "NICE"
Output: Pattern found at index 10
Input: txt = "XYZXACAADXYZXYZX"
   pattern = "XYZX"
Output: Pattern found at index 0
   Pattern found at index 9
   Pattern found at index 12

Rabin-Karp ialah satu lagi algoritma carian corak. Hanya padanan rentetan Algoritma yang dicadangkan oleh Rabin dan Karp untuk mencari corak dengan lebih cekap Cara. Seperti algoritma naif, ia juga menyemak corak dengan menggerakkan tetingkap Ia mencari cincang satu demi satu, tetapi tidak perlu menyemak semua aksara dalam semua kes. Apabila cincang sepadan, setiap aksara disemak. Dengan cara ini, hanya terdapat satu perbandingan bagi setiap urutan teks, menjadikannya algoritma carian corak yang lebih cekap.

Masa prapemprosesan - O(m)

Kerumitan masa algoritma Rabin-Karp ialah O(m+n ) , tetapi untuk senario terburuk, Ia adalah O(mn).

Algoritma

rabinkarp_algo(teks, corak, perdana)

Input#🎟#🎜🎜🎜🎜🎜🎜🎜 corak, perdana)

Input

kuat>− Teks dan corak. Cari nombor perdana lain pada kedudukan cincang

Output

− Cari kedudukan corak

Start
   pat_len := pattern Length
   str_len := string Length
   patHash := 0 and strHash := 0, h := 1
   maxChar := total number of characters in character set
for index i of all character in the pattern, do
   h := (h*maxChar) mod prime
for all character index i of pattern, do
   patHash := (maxChar*patHash + pattern[i]) mod prime
   strHash := (maxChar*strHash + text[i]) mod prime
for i := 0 to (str_len - pat_len), do
   if patHash = strHash, then
      for charIndex := 0 to pat_len -1, do
         if text[i+charIndex] ≠ pattern[charIndex], then
         break
if charIndex = pat_len, then
   print the location i as pattern found at i position.
if i < (str_len - pat_len), then
   strHash := (maxChar*(strHash &ndash; text[i]*h)+text[i+patLen]) mod prime, then
   if strHash < 0, then
   strHash := strHash + prime
End

Contoh#🎜#🎜##🎜 Demo langsung

#include<stdio.h>
#include<string.h>
int main (){
   char txt[80], pat[80];
   int q;
   printf ("Enter the container string </p><p>");
   scanf ("%s", &txt);
   printf ("Enter the pattern to be searched </p><p>");
   scanf ("%s", &pat);
   int d = 256;
   printf ("Enter a prime number </p><p>");
   scanf ("%d", &q);
   int M = strlen (pat);
   int N = strlen (txt);
   int i, j;
   int p = 0;
   int t = 0;
   int h = 1;
   for (i = 0; i < M - 1; i++)
      h = (h * d) % q;
   for (i = 0; i < M; i++){
      p = (d * p + pat[i]) % q;
      t = (d * t + txt[i]) % q;
   }
   for (i = 0; i <= N - M; i++){
      if (p == t){
         for (j = 0; j < M; j++){
            if (txt[i + j] != pat[j])
            break;
         }
         if (j == M)
            printf ("Pattern found at index %d </p><p>", i);
      }
      if (i < N - M){
         t = (d * (t - txt[i] * h) + txt[i + M]) % q;
         if (t < 0)
            t = (t + q);
      }
   }
   return 0;
}

output

Enter the container string
tutorialspointisthebestprogrammingwebsite
Enter the pattern to be searched
p
Enter a prime number
3
Pattern found at index 8
Pattern found at index 21

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