用于实现滚动哈希的C ++程序
滚动哈希是一种哈希函数，其中，输入在移动通过输入的窗口中被哈希。
Rabin-Karp是滚动哈希的流行应用。Rabin和Karp提出的滚动哈希函数计算一个整数值。对于字符串，整数值是字符串的数值。
通常使用非常简单的滚动哈希函数解释Rabin–Karp字符串搜索算法，该函数仅使用乘法和加法-
H=c1ak-1+c2ak-2+….+ cka0.
其中，a为常数，c1，c2….ck为输入字符。为了操纵H的巨大值，完成了modn。
算法
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