数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++ 程序实现滚动哈希
滚动哈希是一种哈希函数，其中输入在遍历输入的窗口中进行哈希。
Rabin-Karp 是滚动哈希的流行应用。Rabin 和 Karp 提出的滚动哈希函数计算一个整数值。对于一个字符串，整数值是一个字符串的数字值。
Rabin-Karp 字符串搜索算法通常使用一个非常简单的滚动哈希函数，该函数仅使用乘法和加法 -
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
更新日期：30-Jul-2019
1 千次浏览
广告