C Chương trình cho thuật toán Rabin-Karp để tìm kiếm mẫu

Đối sánh mẫu trong C - Chúng ta phải tìm xem một chuỗi có xuất hiện trong một chuỗi khác hay không, ví dụ như chuỗi "thuật toán" có trong chuỗi "thuật toán ngây thơ". Nếu nó được tìm thấy, thì vị trí của nó (tức là vị trí mà nó hiện diện) là được hiển thị. Chúng tôi có xu hướng tạo một hàm nhận mảng 2 ký tự và trả về vị trí nếu đối sánh xảy ra, ngược lại trả về -1.

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 là một thuật toán tìm kiếm mẫu khác. Đó là thuật toán so khớp chuỗi được đề xuất bởi Rabin và Karp để tìm ra mẫu theo cách hiệu quả hơn. Giống như Thuật toán Naive, nó cũng kiểm tra mẫu bằng cách di chuyển từng ô cửa sổ, nhưng không cần kiểm tra tất cả các ký tự cho tất cả các trường hợp, nó sẽ tìm giá trị băm. Khi giá trị băm được khớp, thì chỉ nó tiến hành kiểm tra từng ký tự. Bằng cách này, chỉ có một phép so sánh cho mỗi dãy văn bản khiến nó trở thành một thuật toán hiệu quả hơn để tìm kiếm mẫu.

Thời gian tiền xử lý- O (m)

Độ phức tạp về thời gian của Thuật toán Rabin-Karp là O (m + n) , nhưng trong trường hợp xấu nhất, đó là O (mn) .

Thuật toán

rabinkarp_algo (văn bản, mẫu, số nguyên tố)

Đầu vào - Các văn bản chính và các mẫu. Một số nguyên tố khác của tìm vị trí băm

Đầu ra - vị trí, nơi mẫu được tìm thấy

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 – text[i]*h)+text[i+patLen]) mod prime, then
   if strHash < 0, then
   strHash := strHash + prime
End

Ví dụ

#include<stdio.h>
#include<string.h>
int main (){
   char txt[80], pat[80];
   int q;
   printf ("Enter the container string \n");
   scanf ("%s", &txt);
   printf ("Enter the pattern to be searched \n");
   scanf ("%s", &pat);
   int d = 256;
   printf ("Enter a prime number \n");
   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 \n", i);
      }
      if (i < N - M){
         t = (d * (t - txt[i] * h) + txt[i + M]) % q;
         if (t < 0)
            t = (t + q);
      }
   }
   return 0;
}

Đầu ra

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