राबिन-कार्प एल्गोरिदम

राबिन-कार्प पैटर्न खोज का एक और एल्गोरिदम है जो पैटर्न को अधिक कुशल तरीके से ढूंढता है। यह भी विंडो को एक-एक करके मूव करके पैटर्न की जांच करता है, लेकिन सभी केस के लिए सभी कैरेक्टर की जांच किए बिना, यह हैश मान ढूंढता है। जब हैश मान मेल खाता है, तभी यह प्रत्येक कैरेक्टर की जांच करने का प्रयास करता है। यह प्रक्रिया एल्गोरिदम को अधिक कुशल बनाती है।

समय जटिलता O(m+n) है, लेकिन सबसे खराब स्थिति में, यह O(mn) है।

इनपुट और आउटपुट

इनपुट: मुख्य स्ट्रिंग: "ABAAABCDBBABCDDEBCABC", पैटर्न "ABC" आउटपुट: पैटर्न स्थान पर मिला: 4 पैटर्न स्थान पर मिला: 10 पैटर्न स्थान पर मिला: 18

एल्गोरिदम

rabinKarpSearch(text, pattern, prime)

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

आउटपुट - वह स्थान जहां पैटर्न मिले

Begin 
  patLen := pattern Length 
  strLen := string Length 
  patHash := 0 and strHash := 0, h := 1 
  maxChar := 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

आउटपुट
Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18