पैटर्न खोज के लिए राबिन-कार्प एल्गोरिथम के लिए सी कार्यक्रम

सी में पैटर्न मिलान - हमें यह पता लगाना है कि क्या कोई स्ट्रिंग किसी अन्य स्ट्रिंग में मौजूद है, उदाहरण के तौर पर, स्ट्रिंग "एल्गोरिदम" स्ट्रिंग "naive algorithm" के भीतर मौजूद है। यदि यह पाया जाता है, तो इसका स्थान (यानी जिस स्थिति में यह मौजूद है) है प्रदर्शित होता है। हम एक ऐसा फ़ंक्शन बनाते हैं जो 2 कैरेक्टर एरे प्राप्त करता है और यदि मिलान होता है तो स्थिति लौटाता है अन्यथा -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

राबिन-कार्प एक और पैटर्न खोज एल्गोरिथ्म है। यह स्ट्रिंग मिलान एल्गोरिथ्म है जिसे राबिन और कार्प द्वारा अधिक कुशल तरीके से पैटर्न खोजने के लिए प्रस्तावित किया गया था। Naive Algorithm की तरह, यह भी विंडो को एक-एक करके ले जाकर पैटर्न की जाँच करता है, लेकिन सभी मामलों के लिए सभी वर्णों की जाँच किए बिना, यह हैश मान पाता है। जब हैश मान का मिलान किया जाता है, तब ही यह प्रत्येक वर्ण की जाँच करने के लिए आगे बढ़ता है। इस तरह, प्रति पाठ बाद में केवल एक तुलना होती है जो इसे पैटर्न खोज के लिए अधिक कुशल एल्गोरिथम बनाती है।

प्रीप्रोसेसिंग समय- O(m)

राबिन-कार्प एल्गोरिथम की समय जटिलता O(m+n) . है , लेकिन सबसे खराब स्थिति के लिए, यह O(mn) . है ।

एल्गोरिदम

rabinkarp_algo(पाठ, पैटर्न, प्रधान)

इनपुट - मुख्य पाठ और पैटर्न। हैश स्थान खोजने का एक और अभाज्य संख्या

आउटपुट − स्थान, जहां पैटर्न पाया जाता है

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

उदाहरण

#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;
}

आउटपुट

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