রাবিন-কার্প অ্যালগরিদম

Rabin-Karp হল আরেকটি প্যাটার্ন সার্চিং অ্যালগরিদম যাতে প্যাটার্নটিকে আরও দক্ষ উপায়ে খুঁজে বের করা যায়। এটি একের পর এক উইন্ডো সরানোর মাধ্যমে প্যাটার্নটিও পরীক্ষা করে, কিন্তু সমস্ত ক্ষেত্রে সমস্ত অক্ষর পরীক্ষা না করে, এটি হ্যাশ মান খুঁজে পায়। যখন হ্যাশ মান মিলে যায়, তখনই এটি প্রতিটি অক্ষর চেক করার চেষ্টা করে। এই পদ্ধতিটি অ্যালগরিদমকে আরও দক্ষ করে তোলে৷

সময়ের জটিলতা হল O(m+n), কিন্তু সবচেয়ে খারাপ ক্ষেত্রে এটি হল O(mn)।

ইনপুট এবং আউটপুট

Input:
Main String: “ABAAABCDBBABCDDEBCABC”, Pattern “ABC”
Output:
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

অ্যালগরিদম

rabinKarpSearch(text, pattern, prime)

ইনপুট - মূল পাঠ্য এবং প্যাটার্ন। হ্যাশ অবস্থান খোঁজার আরেকটি প্রধান সংখ্যা

আউটপুট - অবস্থান যেখানে নিদর্শন পাওয়া যায়

Begin
   patLen := pattern Length
   strLen := string Length
   patHash := 0 and strHash := 0, h := 1
   maxChar := total number of characters in character set

   for index i of all character in pattern, do
      h := (h*maxChar) mod prime
   done

   for all character index i of pattern, do
      patHash := (maxChar*patHash + pattern[i]) mod prime
      strHash := (maxChar*strHash + text[i]) mod prime
   done

   for i := 0 to (strLen - patLen), do
      if patHash = strHash, then
         for charIndex := 0 to patLen -1, do
            if text[i+charIndex] ≠ pattern[charIndex], then
               break the loop
         done

         if charIndex = patLen, then
            print the location i as pattern found at i position.
      if i < (strLen - patLen), then
         strHash := (maxChar*(strHash – text[i]*h)+text[i+patLen]) mod prime, then
      if strHash < 0, then
         strHash := strHash + prime
   done
End

উদাহরণ

#include<iostream>
#define MAXCHAR 256
using namespace std;

void rabinKarpSearch(string mainString, string pattern, int prime, int array[], int *index) {
   int patLen = pattern.size();
   int strLen = mainString.size();
   int charIndex, pattHash = 0, strHash = 0, h = 1;

   for(int i = 0; i<patLen-1; i++) {
      h = (h*MAXCHAR) % prime;    //calculating h = {d^(M-1)} mod prime
   }
   
   for(int i = 0; i<patLen; i++) {
      pattHash = (MAXCHAR*pattHash + pattern[i]) % prime;    //pattern hash value
      strHash = (MAXCHAR*strHash + mainString[i]) % prime;   //hash for first window
   }
   
   for(int i = 0; i<=(strLen-patLen); i++) {
      if(pattHash == strHash) {      //when hash values are same check for matching
         for(charIndex = 0; charIndex < patLen; charIndex++) {
            if(mainString[i+charIndex] != pattern[charIndex])
               break;
         }

         if(charIndex == patLen) {    //the pattern is found
            (*index)++;
            array[(*index)] = i;
         }
      }

      if(i < (strLen-patLen)) {    //find hash value for next window
         strHash = (MAXCHAR*(strHash - mainString[i]*h) + mainString[i+patLen])%prime;
         if(strHash < 0) {
            strHash += prime;    //when hash value is negative, make it positive
         }
      }
   }
}

int main() {
   string mainString = "ABAAABCDBBABCDDEBCABC";
   string pattern = "ABC";
   int locArray[mainString.size()];
   int prime = 101;
   int index = -1;
   rabinKarpSearch(mainString, pattern, prime, locArray, &index);

   for(int i = 0; i <= index; i++) {
      cout << "Pattern found at position: " << locArray[i]<<endl;
   }
}

আউটপুট

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18