रोलिंग हैश एक हैश फ़ंक्शन है जिसमें इनपुट को एक विंडो में हैश किया जाता है जो इनपुट के माध्यम से चलता है।
राबिन-कार्प रोलिंग हैश का लोकप्रिय अनुप्रयोग है। राबिन और कार्प द्वारा प्रस्तावित रोलिंग हैश फ़ंक्शन एक पूर्णांक मान की गणना करता है। एक स्ट्रिंग के लिए पूर्णांक मान एक स्ट्रिंग का संख्यात्मक मान होता है।
राबिन-कार्प स्ट्रिंग सर्च एल्गोरिथम को अक्सर एक बहुत ही सरल रोलिंग हैश फ़ंक्शन का उपयोग करके समझाया जाता है जो केवल गुणा और जोड़ का उपयोग करता है -
H=c1ak-1+c2ak-2+….+ cka0.
जहाँ, a एक स्थिरांक है, और c1 , सी<उप>2 ….c<उप>के इनपुट वर्ण हैं। 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