1. 哈希（hash）简介
1.1 前言
又来写算法总结了qwq。
今天是 2023/7/8，期末考试已经考完了。初二下注定是一个煎熬的学期，所以我在这一学期并没有学什么新算法，OI 也没什么长进。但倒是深造了几个算法，比如：dp，hash，线段树。
之前一直想写一篇 hash 的学习笔记，但由于种种原因，并没有写成。于是，就在今天，卷完了一天的 whk 过后，我便开始肝 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 p1in [0,mod1-1] pmod{mod1})
且 (p2 in mathbb{N^+}，forall p2in [0,mod2-1] pmod{mod2})
所以，在模 (mod1) 意义下的哈希值冲突的概率为 (sumlimits_{i=1}^ndfrac{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) 意义下的哈希值值域为 (prodlimits_{i=1}^{n1}mod1_i)，模 (mod2) 意义下下的哈希值值域为 (prodlimits_{i=1}^{n2}mod2_i)
所以，模 (mod1) 意义下的哈希值冲突的概率为 (dfrac{1}{prodlimits_{i=1}^{n1}mod1_i})，在模 (mod2) 意义下的哈希值冲突的概率为 (dfrac{1}{prodlimits_{i=1}^{n2}mod2_i})
因为 (prodlimits_{i=1}^{n1}mod1_i < prodlimits_{i=1}^{n2}mod2_i)，所以 (dfrac{1}{prodlimits_{i=1}^{n1}mod1_i} > dfrac{1}{prodlimits_{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 = sumlimits_{j=1}^i S_j times H^{i-j} $
递推式为：
(begin{cases}sum_0=0\sum_i=sum_{i-1}*H+S_iend{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 单哈希
容错率较高，但相对来说代码易实现。
具体证明可参考 2.2 如何解决哈希冲突 这一章的相关证明。
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 桶哈希
桶哈希的本质是一个“桶”，这个桶很特殊，接下来看看普通桶和桶哈希的时间复杂度区别：
| 操作 | 普通桶 | 桶哈希 |
|---|---|---|
| 单点修改 | (O(1)) | (O(1)) |
| 区间修改 | (O(n)) | 最坏(O(n)) |
| 单点查询 | (O(1)) | 不支持 |
| 区间查询 | (O(n)) | 不支持 |
| 全局查询 | (O(n)) | (O(1)) |
这样，桶哈希和普通桶的优势与劣势显而易见。
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) 为 (111dots11) 这样的全 (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^2log 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; } 
