1. 哈希（hash）简介
1.1 前言
又来写算法总结了qwq。
今天是 2023/7/8，期末考试已经考完了。初二下注定是一个煎熬的学期，所以我在这一学期并没有学什么新算法，OI 也没什么长进。但倒是深造了几个算法，比如：dp，hash，线段树。
之前一直想写一篇 hash 的学习笔记，但由于种种原因，并没有写成。于是，就在今天，，我便开始肝 hash 的学习笔记。
本篇主要介绍 hash 的进阶用法，不过也适合 hash 入门（）。如果写假了，就图一乐子qwq。
感谢 @ben093002 对此学习笔记给予结论证明以及鼓励与支持！
好了，正片开始！
1.2 什么是哈希？
哈希算法（Hash Algorithm），又称散列算法。有两种用法，第一种就是将一字符串转化成任意进制的数，目的是方便存储。第二种就是将大范围的数映射成小范围的数，目的也是方便存储。
用第一种打一个比方：
比如要将 ioiakyzy 转成 29 进制的数：
将每一位字母偏移，设偏移量为字母 a 所对应的 ASCLL码 - 1，则字母 a 的原数为 1，字母 b 的原数为 2，字母 c 的原数为 3，\(\dots\)，以此类推；
通过 1 可知，原字符串可转化为 9(15)91(11)(25)(26)(25)；
将 9(15)91(11)(25)(26)(25) 转成 29 进制数：
所以 ioiakyzy 在 29 进制下的 hash 值为 164356834301。
操作 1 的 “字母偏移” 完全可以不需要，设偏移量仅仅是使哈希值的值域变小，方便存储而已。
第二种的话就不用所说了，因为第二种就是我们熟知的离散化，c++ 的 STL 库中的 map 就有体现。
离散化严格意义上是一种哈希。
2. 哈希冲突
2.1 如何解决哈希冲突
在做字符串转哈希值的时候可能会发生一些突发状况。比如哈希值太大了，long long 已经装不下了。怎么办？第一时间会想到对此哈希值取模。但万一有两个不同的字符串所转出来的哈希值取模过后相同，那可就麻烦了。因为这样，在进行对字符串哈希的一系列操作时正确性无法保证了。
这时，就有两种处理方法：
- 将模数增大；
- 将模数数量增多；
证明法1的可行性：（模数为质数）
设 \(mod1 < mod2\)，且 \(mod1 = mod2 - x (x \in \mathbb{N^+})\)
因为 \(p1 \in \mathbb{N^+}，\forall p1\in [0,mod1-1] \pmod{mod1}\)
且 \(p2 \in \mathbb{N^+}，\forall p2\in [0,mod2-1] \pmod{mod2}\)
所以，在模 \(mod1\) 意义下的哈希值冲突的概率为 \(\sum\limits_{i=1}^n\dfrac{1}{mod1^2}=\dfrac{mod1}{mod1^2}=\dfrac{1}{mod1}\)，模 \(mod2\) 意义下下的哈希值冲突的概率为 \(\dfrac{1}{mod2}\)
因为 \(mod1 < mod2\)，所以 \(\dfrac{1}{mod1} > \dfrac{1}{mod2}\)。
所以模数越大，哈希冲突的概率越小。
证毕。
证明法2的可行性：（模数为质数）
设 \(n1 < n2\)，且有 \(mod1_1,mod1_2, mod1_3, \dots, mod1_{n1}\) 和 \(mod2_1, mod2_2, mod2_3, \dots, mod2_{n2}\) （\(\forall i \leq n1,mod1_i \in \mathbb{N^+}\)，\(\forall j \leq n2,mod2_j \in \mathbb{N^+}\)，\(\forall mod1_i \ne \forall mod2_i\)）
由证明1可知，模 \(mod1\) 意义下的哈希值值域为 \(\prod\limits_{i=1}^{n1}mod1_i\)，模 \(mod2\) 意义下下的哈希值值域为 \(\prod\limits_{i=1}^{n2}mod2_i\)
所以，模 \(mod1\) 意义下的哈希值冲突的概率为 \(\dfrac{1}{\prod\limits_{i=1}^{n1}mod1_i}\)，在模 \(mod2\) 意义下的哈希值冲突的概率为 \(\dfrac{1}{\prod\limits_{i=1}^{n2}mod2_i}\)
因为 \(\prod\limits_{i=1}^{n1}mod1_i < \prod\limits_{i=1}^{n2}mod2_i\)，所以 \(\dfrac{1}{\prod\limits_{i=1}^{n1}mod1_i} > \dfrac{1}{\prod\limits_{i=1}^{n2}mod2_i}\)
所以，模数越多且互不相同的情况下，哈希冲突的概率越小。
证毕。
2.2 解决哈希冲突的注意事项
在 2.1 的一系列证明中都加了一句话：模数为质数。说明模数为质数很重要。
事实也是如此，如果模数为合数，哈希冲突的概率会增加，具体的证明可以看这里。不过没看懂也没关系，这并不影响哈希的学习。就像学习并查集（路径压缩 + 按秩合并）的时候你也不会证明其时间复杂度。
但是要注意，哈希更像是一种骗分的工具，因为它有许多的不确定性在里面，跟模拟退火差不多（或者你写哈希的时候不用模数）。
3. 多种哈希的实现
3.1 字符串哈希
字符串哈希是一种很常见的哈希函数。
现在给你一个问题：给定两个字符串 \(S\)，\(T\)，长度别为 \(n\), \(m\)。求 \(T\) 是否是 \(S\) 的子串。
暴力做法很简单，扫 \(S\)，\(T\) 再 check 即可。时间复杂度 \(O(nm)\)。
其实还能更优，用 KMP 算法可以做到 \(O(n)\)。
但 KMP 不会怎么办。用哈希！！
设 \(sum_i\) 表示字符串 \(S\) 子串 \([1, i]\) 的哈希值。结合 1.2 对哈希的概论，可得：
设哈希进制为 \(H\)，模数为 \(mod\)。可得字符串 \(S\) 的子串哈希通项公式为 $sum_i = \sum\limits_{j=1}^i S_j \times H^{i-j} $
递推式为：
\(\begin{cases}sum_0=0\\sum_i=sum_{i-1}*H+S_i\end{cases}\)
代码实现：
sum[0] = 0;
for (int i = 1; i <= n; i++) {
sum[i] = sum[i-1] * H + S[i] % mod;
}
OK！哈希预处理完成。
现在可以用 \(sum\) 这个字符串哈希做很多很多的操作，比如：
3.1.1 截取子串哈希
怎样截取子串哈希值呢？手推一下就行了。
截取 \([l,r]\) 的哈希值，可以类比前缀和。
\(\sum_{i=l}^r s_i \times H^{r-i}\)
\(= H^{r-i} \times (\sum_{i=1}^r s_i - \sum_{i=1}^{l-1} s_i)\)
\(= \sum_{i=1}^r s_i \times H^{r-i} - \sum_{i=1}^{l-1} s_i \times H^{r-i}\)
\(= \sum_{i=1}^r s_i \times H^{r-i} - H^{r-l+1} \times \sum_{i=1}^{l-1} s_i H^{l-i-1}\)
\(= sum_r - sum_{l-1} \times H^{r-l+1}\)
所以 \([l,r]\) 的哈希值为 \(sum_r - sum_{l-1} \times H^{r-l+1}\)。
不过 \(H^{r-l+1}\) 要快速幂，太麻烦了。所以直接预处理一下 H 的任意次方即可。
由于可能会减出负数，所以减完之后先加mod再模mod就行了。具体实现看代码。
时间复杂度 \(O(1)\)。
代码实现：
预处理
int p[N] = {0};
for (int i = 1; i <= n; i++) {
p[i] = p[i-1] * H % mod;
}
截取子串
int get(int l, int r) {
return (sum[r] % mod - sum[l-1] * p[r-l+1] + mod) % mod;
}
3.1.2 对比两段子串是否相同
很简单，只要结合截取子串操作便能完成。
时间复杂度 \(O(1)\)。
代码实现：
int get(int l, int r) {
return (sum[r] % mod - sum[l-1] * p[r-l+1] + mod) % mod;
}
bool check(int l, int r, int L, int R) {
return get(l,r) == get(L,R);
}
回到最初的问题：给定两个字符串 \(S\)，\(T\)，长度别为 \(n\), \(m\)。求 \(T\) 是否是 \(S\) 的子串。
这下不就很简单了吗？
核心代码实现：
int get(int l, int r) {
return (sum[r] % mod - sum[l-1] * p[r-l+1] + mod) % mod;
}
int main() {
int n, m, sum[N], SUM[N];
char S[N], T[N];
cin >> n >> m;
cin >> S + 1 >> T + 1;
sum[0] = 0;
for (int i = 1; i <= n; i++) {
sum[i] = sum[i-1] * H + S[i] % mod;
}
for (int i = 1; i <= m; i++) {
SUM[i] = SUM[i-1] * H + T[i] % mod;
}
for (int i = 1; i + m - 1 <= n; i++) {
if(get(i, i + m - 1) == SUM[m]) puts("Yes");
else puts("No");
}
return 0;
}
3.1.3 字符串哈希的运用
假如你忘记了马拉车，kmp等字符串算法怎么写了，不妨试一试字符串哈希。
还有就是你可以用其优化 dp，比如这一道题 —— gym104081，可以试着做一做，做完后可能你会对字符串哈希有更深刻的理解。
3.1.4 关于字符串哈希的几种优化方式
3.1.4.1 单哈希
容错率较高，但相对来说代码易实现。
具体证明可参考 这一章的相关证明。
3.1.4.2 双哈希
发现单哈希在某种情况下会寄掉。这时使用双哈希是最好的选择。
可以证明，模数增多可以降低哈希的容错率（冲突概率），此在上文已经证明。
不过写多重哈希可能会导致空间承受不起（不过你不写哈希表就没有关系）。所以，正常哈希不建议写模数数量大于二的哈希。
可以证明，当模数增加一个，离散值域会增加一倍，容错率便会大大下降。
具体实现为用一个 \(pair\) 。第一维记录在模第一个模数的意义下的哈希值，第二维记录在模第二个模数的意义下的哈希值。当两维都对应相等时，哈希值才有可能相等。（其实根本不需要证明，感性理解一下也可以）。
3.1.4.3 自然溢出
你还在因为选不定模数而烦恼吗？你还在因为每次计算都要取模而烦恼吗？
有了自然溢出，你还在担心什么？
如果你把存储哈希值的数组的数据类型改成 unsigned long long。首先，这个东西不支持存储负数，处理方法为将哈希值模一个超大的非素数，使其不会爆 \(long long\) 的符号位。
其实这一步就相当于再给哈希取模的过程。不仅短而好写，而且很简单，每次计算不需要模数。
必须注意的是，自然溢出模的数不是质数这意味着它的冲突率高于质数，不过，由于这个模数足够大，所以可忽略这点区别。
不过缺点就是麻仁，CF 卡这玩意卡出了花样。（在 CF 和 AT 手上自然溢出容错率接近于 \(100\%\)）
3.1.4.4 无错哈希
其实原理很简单，就是我们要记录每一个已经诞生的哈希值，然后对于每一个新的哈希值，我们都可以来判断是否和已有的哈希值冲突，如果冲突，那么可以将这个新的哈希值不断加上一个大质数，直到不再冲突。
比如这一题：P3370 【模板】字符串哈希
就用一个 vector 存储每一次冲突的哈希值，再暴力扫即可。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <climits>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <string>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,r,l) for(int i=r;i>=l;i--)
#define mod 1000003
using namespace std;
inline int read() {
rint x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);putchar(x%10+'0');}
else putchar(x+'0');
return;
}
const int N = 100010;
int n = read(), x, ans;
string s;
vector <string> h[mod];
bool F(int x, const string &s) {
for (auto t : h[x]) {
if(t == s) return 0;
}
h[x].push_back(s);
return 1;
}
signed main() {
For(i,1,n) {
cin >> s;
x = 0;
For(j,0,s.size()-1) {
x = (1ll * x * H + s[j]) % mod;
}
ans += F(x, s);
}
cout << ans << '\n';
return 0;
}
3.2 桶哈希
桶哈希的本质是一个“桶”，这个桶很特殊，接下来看看普通桶和桶哈希的时间复杂度区别：
这样，桶哈希和普通桶的优势与劣势显而易见。
Q：啊？这样看来，普通桶大胜桶哈希？
是的，这样看来，普通桶大胜桶哈希。但换个角度看就不是了：桶哈希实现起来困难，常数大，且正确率不能保障，但全局查询为 O(1)。
不过，它也不是一无是处。如果它的全局查询可以做到 \(O(1)\)。这也证明，桶哈希可以在一些特殊的题中扮演决定性的角色。
比如，桶哈希可以 \(O(1)\) 的时间比较两个桶的状态。但是普通的桶做到这一点要 \(O(n)\)。
其实有一个两者的综合版——权值线段树。它的单点/区间修改/查询单次时间复杂度为 \(O(\log n)\)，可谓是非常的优秀！
桶哈希：啊？？真的如此吗？。
3.2.1 单点修改
设 \(b\) 桶哈希第 \(i\) 位表示 \(i\) 这个数的出现的次数，\(H\) 为进制。\(x\) 为我要在桶中插入的数。
于是就仿照二进制状压的写法，\(b = b + H^{x}\)。然后就没了。
Code:
b += p[x];
ps: 省去了取模操作，\(p_i\) 为预处s理好的 \(H^i\) 的值。
如果要插入多个数，则在 \(p_x\) 前面乘上一个系数即可。
3.2.2 区间修改
重复单点修改操作，时间复杂度为 \(O(n)\)。
但是有些时候区间修改的只是固定的，便可考虑离线记录改变的值。这样可以做到期望 \(O(1)\)。
比如我要说的下一道题目。
3.2.3 经典例题 P8819 [CSP-S 2022] 星战
分析得：每一个点的入度都为 \(1\)，则输出 "YES"，否则输出："NO"。
设一个标准桶 \(POS\) 为 \(111\dots11\) 这样的全 \(1\) 桶。设第 \(i\) 个点的入度为 \(r_i\)，实际桶 \(Hash\) 为当前所有节点的入度个数，显然其长度为 \(n\)，初始第 \(i\) 位为 \(r_i\)。在一次操作后只要 \(POS = Hash\)。则说明其合法。
这一步就体现了桶哈希的强大之处——全局查询为 \(O(1)\) 时间复杂度。
最后附上代码：
#include <bits/stdc++.h>
#define ll long long
#define H 500005
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000000007
#define mod 1000000007
using namespace std;
inline int read() {
rint x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);putchar(x%10+'0');}
else putchar(x+'0');
return;
}
const int N = 5e5 + 10;
vector<int> e[N];
ll n, m, q, p[N], POS, Hash, sum[N], rem[N], r[N];
signed main() {
n = read(), m = read();
p[0] = 1;
For(i,1,n) {
p[i] = (p[i - 1] * H) % MOD;
}
For(i,1,n) POS = POS + 1 * p[i];
For(i,1,m) {
int u = read(), v = read();
e[u].push_back(v);
r[u]++;
}
For(i,1,n) {
for (int j = 0; j < e[i].size(); j++) {
int y = e[i][j];
sum[y] += p[i];
}
}
For(i,1,n) rem[i] = sum[i], Hash += sum[i];
q = read();
while(q--) {
int op = read();
if(op == 1) {
int u = read(), v = read();
Hash -= p[u];
rem[v] -= p[u];
} else if(op == 3) {
int u = read(), v = read();
Hash += p[u];
rem[v] += p[u];
} else if(op == 2) {
int u = read();
Hash -= rem[u];
rem[u] = 0;
} else {
int u = read();
Hash -= rem[u] - sum[u];
rem[u] += sum[u];
}
if(Hash == POS) cout << "YES" << '\n';
else cout << "NO" << '\n';
}
return 0;
}
2. 哈希相关例题
2.1 CF1326D2 Prefix-Suffix Palindrome (Hard version)
Problem
给定若干个字符串 \(S\), 对于每一个字符串，要求选取他的一个前缀（可以为空）和与该前缀不相交的一个后缀（可以为空）拼接成回文串，且该回文串长度最大。求生成的最长回文串是什么。
Solve
可以先做一下小小的分类讨论：
若 \(S\) 有回文前后缀，并且长度相等（比如：abcdfdcecba，abccba就是长度相等的回文前后缀），那么，肯定取这一段前后缀最优。
把 \(s\) 的回文前后缀拿掉后，剩下的部分要么是回文前缀，要么是回文后缀。再把其中长度较长的拼接再回文前后缀的中间即可。
比如：abcdfdcecba，先找出其回文前后缀abccba，剩下的部分为 dfdce，发现有一个回文前缀 dfd，于是把其插入 abccba 的中间，最后答案为：abcdfdcba
再比如：abbaxyzyx，它没有回文前后缀，于是要找回文前缀或后缀就行了。答案为：xyzyx。
找回文前后缀可以用双指针，找回文前缀或后缀可以用 hash，时间复杂度 \(O(Tn)\)，也就是 \(O(\sum |S|)\)。
Code
#include <bits/stdc++.h>
#define int long long
#define H 449
#define rint register int
#define For(i,l,r) for(int i=l;i<=r;++i)
#define FOR(i,r,l) for(int i=r;i>=l;--i)
#define mod 436522843
using namespace std;
const int N = 1e6 + 10;
int T, n, sum[N], pre[N], p[N];
char a[N];
void solve() {
cin >> a + 1;
n = strlen(a + 1);
p[0] = 1;
For(i,1,n) {
p[i] = p[i-1] * H % mod;
}
int l = 0, r = n+1;
while(a[l+1] == a[r-1] && l <= r) {
l++, r--;
}
if(l > r) {
For(i,1,n) cout << a[i];
cout << '\n';
return ;
}
l++, r--;
sum[l-1] = 0, pre[r+1] = 0;
For(i,l,r) {
sum[i] = sum[i-1] * H % mod + (a[i] - 'a' + 1);
sum[i] %= mod;
}
FOR(i,r,l) {
pre[i] = pre[i+1] * H % mod + (a[i] - 'a' + 1);
pre[i] %= mod;
}
int ansl = 0, ansr = 0;
For(i,l,r) {
if(sum[i] == (pre[l] % mod - pre[i+1] * p[i-l+1] % mod + mod) % mod) {
ansl = l, ansr = i;
}
}
FOR(i,r,l) {
if(pre[i] == (sum[r] % mod - sum[i-1] * p[r-i+1] % mod + mod) % mod) {
if(ansr - ansl + 1 < r - i + 1) {
ansl = i, ansr = r;
}
}
}
For(i,1,l-1) cout << a[i];
For(i,ansl,ansr) cout << a[i];
For(i,r+1,n) cout << a[i];
cout << '\n';
}
signed main() {
cin >> T;
while(T--) {
solve();
}
return 0;
}
/*
1
abbaxyzyx
*/
2.2 P4503 [CTSC2014] 企鹅 QQ
Problem
定义若两个账户名称是相似的，当且仅当这两个字符串等长且恰好只有一位不同。例如“Penguin1”和“Penguin2”是相似的，但“Penguin1”和“2Penguin”不是相似的。求在给定的 \(n\) 个账户名称中，有多少对是相似的。
Solve
组合数学 + Hash
预处理出每一个字符串的前后缀 \(Hash\)，再枚举每一位，用组合数学统计合法数对就行。
Code
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define H 27
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007
using namespace std;
inline int read() {
rint x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);putchar(x%10+'0');}
else putchar(x+'0');
return;
}
const int N = 3e4 + 10, M = 205;
int n, L, S;
ull pre[N][M], nxt[N][M], p[N], ans;
char s[N][M];
pair<ull, ull> k[N];
signed main() {
n = read(), L = read(), S = read();
p[0] = 1;
For(i,1,L) p[i] = p[i - 1] * H;
For(i,1,n) {
For(j,1,L) cin >> s[i][j];
For(j,1,L) pre[i][j] = pre[i][j - 1] * H + s[i][j];
FOR(j,L,1) nxt[i][j] = nxt[i][j + 1] * H + s[i][j];
}
For(i,1,L) {
For(j,1,n) {
k[j].first = pre[j][i-1];
k[j].second = nxt[j][i+1];
}
sort(k + 1, k + n + 1);
int l = 1, r = 1;
while(r <= n) {
while(k[l] == k[r] && r <= n) r++;
r--;
ans += (((r - l + 1) * (r - l)) >> 1);
l = r + 1, r++;
}
}
cout << ans << '\n';
return 0;
}
2.3. P7469 [NOI Online 2021 提高组] 积木小赛
Problem
给定两个长度为 \(n\) 的小写字母串 \(s\) 和 \(t\)。求在不同情况下从 \(s\) 中选出一个子序列与 \(t\) 中选出一个子串对应相同的方案数（两种情况不同，当且仅当两序列所选出的字符串在两种情况中不同）。
Solve
枚举 \(t\) 的子串，固定左端点 \(L\)，右端点 \(r\) 递增。同时在 \(s\) 中找是否有子序列与所枚举的字串对应相同。为了方便统计方案数，可以用 \(Hash\) 来判断两种情况是否相同。把 \(Hash\) 值丢到 \(unordered\)_\(set\)，\(set\)，或随便搞一个数组（之后进行 sort 和 unique）里面去。实测只有最后一个方法可以通过。
时间复杂度 \(O(N^2\log n)\)。
Code
#include <bits/stdc++.h>
#define int long long
#define H 37
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
using namespace std;
inline int read() {
rint x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);putchar(x%10+'0');}
else putchar(x+'0');
return;
}
const int N = 3e3 + 10;
const int M = 9e6 + 10;
int n, hs, nxt[N][156], res[M], tot;
char s[N], t[N];
signed main() {
n = read();
For(i,1,n) cin >> s[i];
For(i,1,n) cin >> t[i];
For(i,1,n) {
For(j,i,n) {
if(!nxt[i][s[j]]) nxt[i][s[j]] = j;
}
}
For(i,1,n) {
hs = 0;
int k = 1;
For(j,i,n) {
k = nxt[k][t[j]];
if(!k) break;
hs = 1ll * (hs * H) + (t[j] - 'a' + 1);
res[++tot] = hs;
k++;
}
}
sort(res + 1, res + 1 + tot);
cout << ((unique(res + 1, res + 1 + tot)) - res - 1) << '\n';
return 0;
}