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

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

টাইম কমপ্লেক্সিটি O(m+n), কিন্তু ওৰ্স্ট কেসে O(mn)।

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

ইনপুট: মেইন স্ট্রিং: "ABAAABCDBBABCDDEBCABC", প্যাটার্ন "ABC" আউটপুট: Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18

অ্যালগরিদম

rabinKarpSearch(text, pattern, prime)

ইনপুট - মেইন টেক্সট এবং প্যাটার্ন। হ্যাশ লোকেশন বের করার জন্য একটি প্রাইম নাম্বার।

আউটপুট - প্যাটার্ন যেখানে পাওয়া গেল সেসব লোকেশন

শুরু
  patLen := প্যাটার্ন দৈর্ঘ্য
  strLen := স্ট্রিং দৈর্ঘ্য
  patHash := 0 এবং strHash := 0, h := 1
  maxChar := ক্যারেক্টার সেটে মোট ক্যারেক্টার সংখ্যা
  প্যাটার্নের সব ক্যারেক্টারের ইনডেক্স i-এর জন্য করুন
    h := (h*maxChar) mod prime
  শেষ
  প্যাটার্নের সব ক্যারেক্টার ইনডেক্স i-এর জন্য করুন
    patHash := (maxChar*patHash + pattern[i]) mod prime
    strHash := (maxChar*strHash + text[i]) mod prime
  শেষ
  i := 0 থেকে (strLen - patLen) পর্যন্ত, করুন
    যদি patHash = strHash, তবে
      charIndex := 0 থেকে patLen -1 পর্যন্ত, করুন
        যদি text[i+charIndex] ≠ pattern[charIndex], তবে
          লুপ ব্রেক করুন
      শেষ
      যদি charIndex = patLen, তবে
        লোকেশন i প্রিন্ট করুন যেখানে প্যাটার্ন পাওয়া গেল।
    যদি i < (strLen - patLen), তবে
      strHash := (maxChar*(strHash - text[i]*h)+text[i+patLen]) mod prime, এরপর
      যদি strHash < 0, তবে
        strHash := strHash + prime
  শেষ
শেষ

উদাহরণ

#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; //h = {d^(M-1)} mod prime ক্যালকুলেট করুন } for(int i = 0; i<patLen; i++) { pattHash = (MAXCHAR*pattHash + pattern[i]) % prime; //প্যাটার্ন হ্যাশ ভ্যালু strHash = (MAXCHAR*strHash + mainString[i]) % prime; //প্রথম উইন্ডোর হ্যাশ } for(int i = 0; i<=(strLen-patLen); i++) { if(pattHash == strHash) { //যখন হ্যাশ ভ্যালু একই, ম্যাচিং চেক করুন for(charIndex = 0; charIndex < patLen; charIndex++) { if(mainString[i+charIndex] != pattern[charIndex]) break; } if(charIndex == patLen) { //প্যাটার্ন পাওয়া গেল (*index)++; array[(*index)] = i; } } if(i < (strLen-patLen)) { //নেক্সট উইন্ডোর হ্যাশ ভ্যালু বের করুন strHash = (MAXCHAR*(strHash - mainString[i]*h) + mainString[i+patLen])%prime; if(strHash < 0) { //যখন হ্যাশ ভ্যালু নেগেটিভ, পজিটিভ করুন strHash += prime; } } } } 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