रोलिंग हैश एक हैश फ़ंक्शन है जिसमें इनपुट को एक विंडो में हैश किया जाता है जो इनपुट के माध्यम से चलती है।
रैबिन-कार्प रोलिंग हैश का एक लोकप्रिय अनुप्रयोग है। रैबिन और कार्प द्वारा प्रस्तावित रोलिंग हैश फ़ंक्शन एक पूर्णांक मान की गणना करता है। एक स्ट्रिंग के लिए पूर्णांक मान स्ट्रिंग का संख्यात्मक मान होता है।
रैबिन-कार्प स्ट्रिंग खोज एल्गोरिथम को अक्सर एक बहुत ही सरल रोलिंग हैश फ़ंक्शन का उपयोग करके समझाया जाता है जो केवल गुणन और जोड़ का उपयोग करता है -
H=c1ak-1+c2ak-2+….+ cka0.
जहां, a एक स्थिरांक है, और c1, c2...ck इनपुट वर्ण हैं। H के विशाल मान को संभालने के लिए, mod n किया जाता है।
एल्गोरिथम
Begin Declare a constant variable P_B of the integer datatype. Initialize P_B= 227. Declare a constant variable P_M of the integer datatype. Initialize P_M= 1000005. Declare a hash() function Pass a string s as parameter. Declare r of the integer datatype. Initialize r = 0. for (int i = 0; i < s.size(); i++) r = r* P_B + s[i] r %= P_M return r Declare function rabin_karp(const string& n, const string& hstack) Declare h1 of the integer datatype. Initialize h1 = hash(n). Declare h2 of the integer datatype. Initialize h2 = 0. Declare power of the integer datatype. Initialize power = 1. for (int i = 0; i < n.size(); i++) power = (power * P_B) % P_M for (int i = 0; i < hstack.size(); i++) h2 = h2*P_B + hstack[i] h2 %= P_M if (i >= n.size()) h2 -= power * hstack[i-n.size()] % P_M if (h2 < 0) h2 += P_M if (i >= n.size()-1 && h1 == h2) return i - (n.size()-1); return -1; Declare s1 and s2 to the string type. Print “Enter Input String:” Call getline(line, s1) to enter the string. Print “Enter string to find:” Take input for s2. if(rabin_karp(s2, s1) == -1) print” String not found” else print the string. End.
उदाहरण कोड
#include <iostream> #include <string> using namespace std; const int P_B= 227; const int P_M = 1000005; int hash(const string& s) { int r = 0; for (int i = 0; i < s.size(); i++) { r = r* P_B + s[i]; r %= P_M; } return r; } int rabin_karp(const string& n, const string& hstack) { int h1 = hash(n); int h2 = 0; int power = 1; for (int i = 0; i < n.size(); i++) power = (power * P_B) % P_M; for (int i = 0; i < hstack.size(); i++) { h2 = h2*P_B + hstack[i]; h2 %= P_M; if (i >= n.size()) { h2 -= power * hstack[i-n.size()] % P_M; if (h2 < 0) h2 += P_M; } if (i >= n.size()-1 && h1 == h2) return i - (n.size()-1); } return -1; } int main() { string s1, s2; cout<<"Enter Input String: "; getline(cin, s1); cout<<"Enter String to find: "; cin>>s2; if(rabin_karp(s2, s1) == -1) cout<<"String not found"<<endl; else cout<<"String"<<" "<<s2<<” “<<"found at position "<<rabin_karp(s2, s1)<<endl; return 0; }
आउटपुट
Enter Input String: Tutorialspoint Enter String to find: a String a found at position 6 Enter Input String: Tutorialspoint Enter String to find: b String not found
