哈希
用于比较两个字符串是否相等；
本质就是把一个字符串看成一个base进制的数（base自定），每一位是这一位的字符对应的 $ ASCII $ 值，在比较时只需判断这两个数（即哈希值）是否相等即可；
一般的，base会选一个质数（200+即可），很容易发现，一个字符串的哈希值是很大的，所以要进行取模；
Hash冲突
当Hash值映射的范围很小时（如1e9 + 7），有可能出现两个不同的字符串Hash值相等的情况，这就是Hash冲突；
Hash一般采用的打法有两种：
自然溢出Hash
我们都知道，当一个数超出了这个数的数据范围时会溢出，那么我们就可以利用这个特性，再求Hash值的时候使其溢出，又因为Hash值非负（根据定义），所以采用 $ unsigned $ 类型存储（一般为 $ unsigned \ long \ long $）；
优点：代码简便；
缺点：容易被卡（这相当于使出题人知道了你的模数，可以构建特殊数据造成Hash冲突）；
例题：给出字母表 $ {'A','B','C',...,'Z'} $ 和两个仅有字母表中字母组成的有限字符串：单词 $ W $ 和文章 $ T $，找到 $ W $ 在 $ T $ 中出现的次数。这里“出现”意味着 $ W $ 中所有的连续字符都必须对应 $ T $ 中的连续字符。$ T $ 中出现的两个 $ W $ 可能会部分重叠。
从左往右遍历 $ T $ 中每个长度为 $ |W| $ 的字串并和 $ W $ 逐个比较；
这里可以运用前缀和优化，具体看代码：
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
const unsigned long long pep = 229;
int t;
string a, b;
unsigned long long h[10000005];
unsigned long long p[10000005];
unsigned long long get_hash(string x) {
unsigned long long ans = 0;
for (int i = 0; i < x.size(); i++) {
ans = (ans * pep + x[i]); //暴力求Hash值，一位一位的加入（类比十进制）；
}
return ans;
}
int main() {
cin >> t;
p[0] = 1; //p[i]代表进制pep的i次方；
for (int i = 1; i <= 100005; i++) p[i] = (p[i - 1] * pep);
while(t--) {
int ans = 0;
memset(h, 0, sizeof(h));
cin >> a >> b;
unsigned long long c = get_hash(a);
int lena = a.size();
h[1] = b[0];
h[0] = 0;
for (int i = 2; i <= b.size(); i++) {
h[i] = (h[i - 1] * pep + b[i - 1]); //这里的h数组相当于一个前缀和，这样就可以每次 O(1)求出其子串的Hash值了；
}
for (int i = lena; i <= b.size(); i++) {
unsigned long long d = 0;
d = (h[i] - h[i - lena] * p[lena]); //这里可以类比十进制；
if (d == c) ans++;
}
cout << ans << endl;
}
return 0;
}
双模数Hash
用单模数很容易造成Hash冲突，原因就在于Hash值的值域太小，所以我们可以考虑双模数Hash；
双模数Hash本质上就是用两个不同的模数计算两个字符串的Hash值，如果这两个Hash值分别相等，则这两个字符串相等；
这样值域就扩大到了两个模数相乘的范围，一般两个模数在 $ int $ 范围内即可；
当然，两个模数在 $ long \ long $ 范围内也行，只不过 $ long \ long $ * $ long \ long $ 需要用到快速乘，容易超时，所以一般不用；
好像模数需要是质数（貌似是因为 $ CRT $ ），但好像不是质数也行（这里参考别的博客吧）；
例题：和上面一样；
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
const long long mod1 = 99999885229;
const long long mod2 = 99999886229;
const long long pep = 229;
int t; //以下各数组和上面的意义一样；
string a, b;
long long h[10000005];
long long p[10000005];
long long pp[10000005];
long long hh[10000005];
long long ksc(long long a, long long b, long long pp) { //快速乘；
long long ans = 0;
while(b) {
if (b & 1) ans = (ans + a) % pp;
b >>= 1;
a = (a + a) % pp;
}
return ans;
}
long long get_hash(string x) {
long long ans = 0;
for (int i = 0; i < x.size(); i++) {
ans = (ksc(ans, pep, mod1) + x[i] % mod1) % mod1;
}
return ans;
}
long long get_hash1(string x) {
long long ans = 0;
for (int i = 0; i < x.size(); i++) {
ans = (ksc(ans, pep, mod2) + x[i] % mod2) % mod2;
}
return ans;
}
int main() {
cin >> t;
p[0] = 1;
pp[0] = 1;
for (int i = 1; i <= 100005; i++) p[i] = ksc(p[i - 1], pep, mod1);
for (int i = 1; i <= 100005; i++) pp[i] = ksc(pp[i - 1], pep, mod2);
while(t--) {
int ans = 0;
memset(h, 0, sizeof(h));
memset(hh, 0, sizeof(hh));
cin >> a >> b;
long long c = get_hash(a);
long long e = get_hash1(a);
int lena = a.size();
h[1] = b[0];
h[0] = 0;
hh[0] = 0;
hh[1] = b[0];
for (int i = 2; i <= b.size(); i++) {
h[i] = (ksc(h[i - 1], pep, mod1) + b[i - 1] % mod1) % mod1;
}
for (int i = 2; i <= b.size(); i++) {
hh[i] = (ksc(hh[i - 1], pep, mod2) + b[i - 1] % mod2) % mod2;
}
for (int i = lena; i <= b.size(); i++) {
long long d = 0;
long long d1 = 0;
d = (h[i] % mod1 - ksc(h[i - lena], p[lena], mod1) + mod1) % mod1;
d1 = (hh[i] % mod2 - ksc(hh[i - lena], pp[lena], mod2) + mod2) % mod2;
if (d == c && d1 == e) ans++;
}
cout << ans << endl;
}
return 0;
}
在 $ |W| <= |T| <= 1000000 $ 的情况下，这个代码会超时（因为有快速乘），所以模数尽量开 $ int $ 内的；
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
const long long mod1 = 1e9 + 7;
const long long mod2 = 998244353;
const long long pep = 229;
int t; //以下各数组和上面的意义一样；
string a, b;
long long h[10000005];
long long p[10000005];
long long pp[10000005];
long long hh[10000005];
long long ksc(long long a, long long b, long long pp) { //快速乘；
long long ans = 0;
while(b) {
if (b & 1) ans = (ans + a) % pp;
b >>= 1;
a = (a + a) % pp;
}
return ans;
}
long long get_hash(string x) {
long long ans = 0;
for (int i = 0; i < x.size(); i++) {
ans = (ans * pep % mod1 + x[i] % mod1) % mod1;
}
return ans;
}
long long get_hash1(string x) {
long long ans = 0;
for (int i = 0; i < x.size(); i++) {
ans = (ans * pep % mod2 + x[i] % mod2) % mod2;
}
return ans;
}
int main() {
cin >> t;
p[0] = 1;
pp[0] = 1;
for (int i = 1; i <= 100005; i++) p[i] = p[i - 1] * pep % mod1;
for (int i = 1; i <= 100005; i++) pp[i] = pp[i - 1] * pep % mod2;
while(t--) {
int ans = 0;
memset(h, 0, sizeof(h));
memset(hh, 0, sizeof(hh));
cin >> a >> b;
long long c = get_hash(a);
long long e = get_hash1(a);
int lena = a.size();
h[1] = b[0];
h[0] = 0;
hh[0] = 0;
hh[1] = b[0];
for (int i = 2; i <= b.size(); i++) {
h[i] = (h[i - 1] * pep % mod1 + b[i - 1] % mod1) % mod1;
}
for (int i = 2; i <= b.size(); i++) {
hh[i] = (hh[i - 1] * pep % mod2 + b[i - 1] % mod2) % mod2;
}
for (int i = lena; i <= b.size(); i++) {
long long d = 0;
long long d1 = 0;
d = (h[i] % mod1 - h[i - lena] * p[lena] % mod1 + mod1) % mod1;
d1 = (hh[i] % mod2 - hh[i - lena] * pp[lena] % mod2 + mod2) % mod2;
if (d == c && d1 == e) ans++;
}
cout << ans << endl;
}
return 0;
}