滚动哈希（Rabin

Rabin_Karp算法利用哈希的特性，求出子串的哈希值，可以用来寻找某串是否在字符串中出现以及个数。 例如 给出文本串 aaabbc 模式串 ab 询问 模式串  是否在 文本串中 出现过  ，可以求出文本串中长度为2的子串的哈希值， 即 aa aa ab bb bc ，再求出 模式串ab的哈希值， 通过比较哈希值判断是否出现过。 求哈希值时，若按位求子串哈希值，复杂度为n * m。 若使用Rabin_Karp算法，可以降为 n + m。 就以求 abcaabc 的长度k为 3 的子串 为例 定义 r = p^k​​​​​​​​​​​​ abc的哈希值为 s[0] * p * p + s[1] * p + s[2]; bca的哈希值为 s[1] * p * p + s[2] * p + s[3]; 显然bca的哈希值可以由s[0] * p * p * p + s[1] * p * p + s[2] * p + s[3] - s[0] * p * p * p 即h[2] * p + s[3] - s[3 - 3] * r 得到； caa的哈希值为 s[2] * p * p + s[3] * p + s[4]; 可以由 s[1] * p * p * p + s[2] * p * p + s[3] * p + s[4] - s[1] * p * p * p 即h[3] * p + s[4] - s[4 - 3] * r 得到； 这里就可以推出Rabin_Karp算法的原理； h = h * p + s[i] - s[i - k] * r; (i为该子串最后位置的下标) 实现时，先计算出r， 即是p 的 k次方（子串的长度）； 然后计算下一组时 去掉前一位再加上后面一位； 这时复杂度即为n + m； 至于撞哈希， emm看运气吧

以一道例题为例

POJ -1200 Crazy Search

http://poj.org/problem?id=1200

题意是给出一个n， 一个m， 再给出一个字符串，询问在字符串中长度为n的不同子串个数；

m为给出的串中，不同字符的个数，emmm 没啥用；

直接上代码了

#include<iostream> #include<vector> #include<stdio.h> #include<algorithm> using namespace std; typedef unsigned long long ull; vector<ull>v; int main(){ int n, m; cin >> n >> m; string s; cin >> s; int len = s.size(); ull p = 1e9 + 9, r = 1, h = 0; for(int i = 0; i < n && i < len; i++) // 先求前k位，算出r h = h * p + s[i], r *= p; if(len >= n) // 如果原串长度大于k， 即先前求的k位是其子串， 加入集合 v.push_back(h); for(int i = n; i < len; i++) // 计算k位以后的子串， 过程即是上面的介绍。 h = h * p + s[i] - s[i - n] * r, v.push_back(h); sort(v.begin(), v.end()); // 排序为了下面的去重 v.erase(unique(v.begin(), v.end()), v.end()); // 去重 cout << v.size() << endl; // 输出大小 即是答案 return 0; }

再来一道实践的， 找出模式串在文本串中出现的个数。

emmm， 听起来像kmp；

ZZULIOJ 1270: 剪花布条

http://acm.zzuli.edu.cn/problem.php?id=1270

#include<iostream> #include<vector> #include<stdio.h> #include<algorithm> using namespace std; typedef unsigned long long ull; vector<ull>v; int main(){ string s, b; while (cin >> s, s != "#") { cin >> b; int len = s.size(); int k = b.size(); int cnt = 0; ull p = 1e9 + 9, r = 1, h = 0, c = 0; for(int i = 0; i < len && i < k; i++) h = h * p + s[i], r *= p; if(len >= k) v.push_back(h); for(int i = k; i < len; i++) h = h * p + s[i] - s[i - k] * r, v.push_back(h); // 与上面的算法相同求出文本串每个位置的哈希值 for(int i = 0; i < k; i++) // 求出模式串的哈希值 c = c * p + b[i]; for(int i = 0; i < v.size(); i++) { if(v[i] == c) // 如果当前位置的哈希值等于模式串， 即是相同， cnt++, i += k - 1; // 注意这题是不能共用同一个字符， 所以i 要加上k， 后面又i++了， 所以i += k - 1； } cout << cnt << endl; v.clear(); } return 0; }

看懂了可以再找几道题练练