প্যাটার্ন অনুসন্ধানের জন্য রবিন-কার্প অ্যালগরিদমের জন্য সি প্রোগ্রাম

C-তে প্যাটার্ন ম্যাচিং − আমাদের খুঁজে বের করতে হবে যদি একটি স্ট্রিং অন্য একটি স্ট্রিং-এ উপস্থিত থাকে, উদাহরণস্বরূপ, স্ট্রিং "অ্যালগরিদম" স্ট্রিং "নেইভ অ্যালগরিদম" এর মধ্যে উপস্থিত রয়েছে। যদি এটি পাওয়া যায়, তাহলে এর অবস্থান (অর্থাৎ এটি যে অবস্থানে রয়েছে) প্রদর্শিত। আমরা এমন একটি ফাংশন তৈরি করার প্রবণতা রাখি যা 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 অ্যালগরিদমের মতো, এটিও একটি করে windowone সরানোর মাধ্যমে প্যাটার্ন পরীক্ষা করে, কিন্তু সমস্ত ক্ষেত্রে সমস্ত অক্ষর পরীক্ষা না করে, এটি হ্যাশ মান খুঁজে পায়। যখন হ্যাশ মান মিলে যায়, তখনই এটি প্রতিটি অক্ষর পরীক্ষা করতে এগিয়ে যায়। এইভাবে, প্রতি টেক্সট অনুগামীতে শুধুমাত্র একটি তুলনা এটি প্যাটার্ন অনুসন্ধানের জন্য আরও দক্ষ অ্যালগরিদম তৈরি করে৷

প্রি-প্রসেসিং টাইম- 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