滚动哈希是一种哈希函数,其中,输入在移动通过输入的窗口中被哈希。
Rabin-Karp是滚动哈希的流行应用。Rabin和Karp提出的滚动哈希函数计算一个整数值。对于字符串,整数值是字符串的数值。
通常使用非常简单的滚动哈希函数解释Rabin–Karp字符串搜索算法,该函数仅使用乘法和加法-
H=c1ak-1+c2ak-2+….+ cka0.
其中,a为常数,c 1,c 2 ….c k为输入字符。为了操纵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: Nhooo Enter String to find: a String a found at position 6 Enter Input String: Nhooo Enter String to find: b String not found