字符串哈希（hash）
今天我们来看一个叫字符串哈希的算法 顾名思义，这是用来字符串匹配的算法
一、进制
通过对各种进制的观察，我们不难发现：
任意一个 R进制的数，都可以看成是一个满足如下条件的字符串：
每个位上都是 [0,R−1]之间的一个数字；两个字符串相等，当且仅当这两个字符串代表的 R进制数相等。
判断两个字符串相等，需要一层循环，是 O(n)
的，而判断两个数相等，是 O(1)的。
所有英文字母的取值范围都在 128以内，因此，每个英文字母均可以看成是一个 R(R≥128) 进制数的基数值，任意一个字符串均可看作有一个或多个位的 R 进制数。
H(“abcd”)=97⋅R3+98⋅R2+99⋅R+100 H(“ab”)=97⋅R+98 H(“cd”)=99⋅R+100=H(abcd)−H(ab)⋅R2
不难看出，在已知某个字符串的所有前缀的 R 进制数值的前提下，计算任意一个子串的 R 进制数值只需 O(1) 的时间（当然还需要预处理出 Ri 的值）。
至此，对于上面的题目，我们可以：把 B
转为一个 R 进制数 hb，时间复杂度为 O(n) 。 逐一枚举 A 中的位置 i，预处理出 A 的前 i 位构成的 R 进制数的数值 h[i]，时间复杂度为 O(n) 。 逐一枚举 A 中的位置 i，用 O(1) 的时间求出 A 中从第 i 个位开始的与 B 相同的一个字符串对应的 R 进制数 ha，检查是否满足 hb=ha
按照这个思路，整个算法的时间复杂度就降到了 O(n)，可以通过了。
但是等等，这里好像有一个问题：由于 R 是大于等于 128 的数，Ri 很容易就会超出 int 甚至 long long 的取值范围，我们根本无法存储。而如果采用大整数来运算及存储，就得不偿失了。 我们继续思考如何解决这个问题
二、散列
设计这种散列函数一定要简单且快，通常采用经典的“除留余数法”，为了减少冲突，我们需要做 2件事情：要让余数的取值范围尽量大（采用最大的数据类型 unsigned long long，相当于模 2^64)
R选取一个大于 128 的素数，例如：131,13331
等等。H(“abcd”)=97×1313+98×1312+99×131+100 =218064827+1681778+12969+100 =219746605
那么，上面为什么没有去模 2^64 呢？因为 unsigned long long 本身恰好就是 64 位，它计算出来的结果本来就是只保留小于 2^64的部分，这称作自然溢出。 好啦！到此为止，我们就完成了真个算法设计，看看代码吧！
#include <iostream>
#include <cstring>
using namespace std;
using ULL = unsigned long long;
const int N = 1e6 + 7, P = 131;
ULL sum[N], sa, pw[N];
char s[N];
int main() {
scanf("%s", s + 1);
pw[0] = 1;
int len = strlen(s + 1);
for (int i = 1; s[i]; ++i) {
sum[i] = sum[i-1] * P + s[i];
pw[i] = pw[i-1] * P;
}
scanf("%s", s + 1);
int lena = strlen(s + 1), ans = 0;
for (int i = 1; s[i]; ++i)
sa = sa * P + s[i];
for (int i = 1; i+lena-1 <= len; ++i) {
ULL d = sum[i+lena-1] - sum[i-1]*pw[lena];
if (d == sa)
++ans;
}
printf("%d", ans);
return 0;
}
三、遗留问题
我们都知道散列一定会出现冲突的，理论上一定存在两个不同字符串的散列值相同，对策有两条：
仅用散列判断两个字符串不同，即若两个字符串的散列值不同，那它们一定是两个不同的字符串。
当两个字符串的散列值相同时，可以采用以下两种策略之一：
1 双哈希，即再用另一个素数计算以下散列，看看是否相同。
2 直接判断，即用循环比对一下字符串是否相同。