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

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

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

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

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

एल्गोरिदम

rabinKarpSearch(text, pattern, prime)

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

आउटपुट - वह स्थान जहाँ पैटर्न पाए जाते हैं

पेटलेन शुरू करें:=पैटर्न लंबाई strLen:=स्ट्रिंग लंबाई patHash:=0 और strHash:=0, h:=1 maxChar:=पैटर्न में सभी वर्णों के सूचकांक i के लिए वर्ण सेट में वर्णों की कुल संख्या, h करें:=(h*maxChar) मॉड प्राइम सभी कैरेक्टर इंडेक्स 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, यदि टेक्स्ट [i + charIndex] पैटर्न [charIndex] करें, तो लूप को तोड़ दें यदि charIndex =patLen, फिर स्थान i को i स्थिति में पाए गए पैटर्न के रूप में प्रिंट करें। अगर मैं <(strLen - patLen), तो strHash :=(maxChar*(strHash - text[i]*h)+text[i+patLen]) mod prime, तो अगर strHash <0, तो strHash :=strHash + prime किया समाप्त

उदाहरण

#include#define MAXCHAR 256नेमस्पेस 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 
आउटपुट
 
पैटर्न स्थिति में मिला:4Pattern स्थिति में मिला:10Pattern स्थिति में मिला:18