C++ 程序实现滚动哈希
c++server side programmingprogramming
滚动哈希是一种哈希函数，其中输入在通过输入移动的窗口中进行哈希处理。
Rabin-Karp 是滚动哈希的流行应用。Rabin 和 Karp 提出的滚动哈希函数计算一个整数值。对于字符串，整数值是字符串的数值。
Rabin–Karp 字符串搜索算法通常使用一个非常简单的滚动哈希函数来解释，该函数仅使用乘法和加法 −
H=c1ak-1+c2ak-2+….+ cka0。
其中，a为常数，c1、c2….ck为输入字符。为了操作H的Huge值，需要对n进行mod。
算法
开始 声明一个整型常量变量P_B。 初始化P_B= 227。 声明一个整型常量变量P_M。 初始化P_M= 1000005。 声明一个hash()函数 传递字符串 s 作为参数。 声明整数数据类型的 r。 初始化 r = 0。 for (int i = 0; i < s.size(); i++) r = r* P_B + s[i] r %= P_M return r 声明函数 rabin_karp(const string& n, const string& hstack) 声明整数数据类型的 h1。 初始化 h1 = hash(n)。 声明整数数据类型的 h2。 初始化 h2 = 0。 声明整数数据类型的 power。 初始化 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 如果 (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; 将 s1 和 s2 声明为字符串类型。 打印"输入字符串:" 调用 getline(line, s1) 输入字符串。 打印"输入要查找的字符串:" 输入 s2。 if(rabin_karp(s2, s1) == -1) 打印"未找到字符串" else 打印字符串。 结束。
示例代码
#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<<"输入输入字符串:";
getline(cin, s1);
cout<<"输入要查找的字符串:";
cin>>s2;
if(rabin_karp(s2, s1) == -1)
cout<<"未找到字符串<<endl;
else
cout<<"字符串"<<" "<<s2<<” “<<"在位置"<<rabin_karp(s2, s1)<<endl;
return 0;
}
输出
输入输入字符串:Tutorialspoint 输入要查找的字符串:a 在位置 6 找到字符串 a 输入输入字符串:Tutorialspoint 输入要查找的字符串:b 未找到字符串
