字符串哈希-育师

引入

定义：
把字符串映射到整数的函数$f$，称$f$为Hash 函数。

从定义可以看出，字符串 Hash 函数的实质是：把每个不同的字符串转化为不同的整数，希望$O(1)$判断两个字符串是否相等。

然而事实上，经常会出现两个不同的字符串映射到相同的 Hash 值的现象，称为哈希冲突。由此引出哈希函数两条最重要的性质。

性质：
在 Hash 函数值不一样时，两个字符串一定不一样；
在 Hash 函数值一样时，两个字符串不一定一样。

对于一个长度为$l$的字符串$s$，定义其多项式 Hash 函数为：$$f(s) = \sum_{i=1}^l s[i] \times p^{l-i} \pmod M$$

可以类比$p$进制数来帮助理解。例如字符串$xyz$，其哈希函数值为$xp^2+yp+z$。下文中的 Hash 函数均采用这种定义方式。

生日悖论

考虑这样一个问题：多少个人里有两个生日相同的人的概率有 50% 呢？答案是反直觉的 23 个人。

证明：设房间里共有$n$个人，排除闰年$366$天的情况。第一个人的生日是$365$选$365$，第二个人的生日是$365$选$364$，第三个人的生日是$365$选$363$。以此类推，第$n$个人的生日是$365$选$365 - n + 1$。

\[P(所有人生日不同) = \frac{365}{365} \times \frac{364}{365} \times \frac{365 - n + 1}{365} = \frac{365!}{365^n(365-n)!} \]

\[P(至少有两人生日相同) = 1 - P(所有人生日不同) \]

说明：
当元素的个数增多时，哈希冲突的概率会以很快的速度增长。

再考虑模数$M$应满足什么条件。因为质数不与其他数字存在公因数，可以减少因取模操作带来的周期性冲突，所以通常选取足够大的质数来作为模数$M$。

方法

对于读入的字符串，习惯于在前加一个空格符调整下标，一般直接采用其 ASCII 码，用数组预处理基数的幂。

自然溢出法

顾名思义，利用无符号长整形/* by 01130.hk - online tools website : 01130.hk/zh/unicode.html */ unsigned long long自然溢出的特性。若数据超出 ull 的存储范围，则结果自然$\pmod {2^{64}}-1$。Hash 公式如下：

/* by 01130.hk - online tools website : 01130.hk/zh/unicode.html */ typedef unsigned long long ull; ull hs[N]; hs[i] = hs[i] * p + s[i];

其中，基数$p$是一个较大的质数，如$233$，$271$，$2333$等，否则唯一性也难以保证。

例题：
产奶模式

题目要求出现了至少$k$次的最大连续子段的长度。

若最终答案为$m$。则这些连续子段去掉末尾元素后仍然相同，即：序列中长为$m-1$的相同连续子段也会出现至少$k$次。可见，连续子段长度为$0$~$m$时都可行，长度为$(m+1)$~$n$时都不可行。答案满足单调性，考虑二分答案。

预处理序列前缀 Hash，在check函数里，遍历所有长度为$mid$的连续子段，对其 Hash 值出现的次数计数。由于 Hash 值较大，不能使用桶数组，可使用map计数。时间复杂度$O(n \log ^ 2 n)$。代码如下：

#include <iostream> #include <map> using namespace std; typedef unsigned long long ull; const int N = 2e4 + 8, p = 233; ull ppow[N], hs[N]; int n, k, a[N]; ull geths(int l, int r) { return hs[r] - hs[l - 1] * ppow[r - l + 1]; } bool check(int mid) { map<ull, ull> mp; for (int l = 1; l + mid - 1 <= n; l++) { ull h = geths(l, l + mid - 1); if (++mp[h] >= k) return true; } return false; } int main() { ppow[0] = 1; for (int i = 1; i < N; i++) ppow[i] = ppow[i - 1] * p; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; hs[i] = hs[i - 1] * p + a[i]; } int l = 0, r = n, mid, ans; while (l <= r) { int mid = l + r >> 1; if (check(mid)) l = mid + 1, ans = mid; else r = mid - 1; } cout << ans; return 0; }

単 Hash 法

注意：単 Hash 法在模数较小的时候，唯一性难以保证。

相当于没有了自动取模特性的自然溢出法，唯一不同就是需要手动加上取模。Hash 公式如下：

hs[i] = (hs[i - 1] * p + s[i]) % mod;

其中$p < mod$且$p$与$mod$是足够大的质数。

双 Hash 法

很稳很安全的 Hash 方法。对比単 Hash 法，双 Hash 法用两个不同的基数$p$进行两次取模$mod$操作。Hash 公式如下：

hs1[i] = (hs1[i] * p + s[i]) % mod1; hs2[i] = (hs2[i] * p + s[i]) % mod2;

判断是否相同时，用一对 Hash 函数值来比较。只要有一个不匹配就说明字符串不相同。cmp函数如下：

bool cmp(string s, string t) { return geths1(s) == geths1(t) && geths2(s) == geths2(t); }

获取子串的 Hash

已知字符串$S$的 Hash 值$hs[i]$，且$|S| = n$。它的子串$S[l..r]$，其中$1 \leq l \leq r \leq n$，对应的 Hash 值为：

((hs[r] - hs[l - 1] * ppow[r - l + 1]) % mod + mod) % mod

推导过程类似于前缀和中的区间和，感兴趣的读者请自行研究。

应用

字符串匹配

例题：
给出两个字符串$S$和$T$，求$T$在$S$中出现的次数。不同位置出现的$T$可重叠。

求出模式串$T$的 Hash 值后，求出文本串$S$中每个长度为$T$长度的字串的 Hash 值，分别于$T$的 Hash 值比较即可。代码如下：

#include <iostream> using namespace std; typedef long long ll; const int p = 233, mod = 1e9 + 7, N = 1e6 + 8; string s, t; ll ppow[N], hsh[N], ths; ll get_hash(int l, int r) { return ((hsh[r] - hsh[l - 1] * ppow[r - l + 1]) % mod + mod) % mod; } int main() { ppow[0] = 1; for (int i = 1; i < N; i++) ppow[i] = ppow[i - 1] * p % mod; cin >> s >> t; int slen = s.size(), tlen = t.size(); s = ' ' + s; t = ' ' + t; for (int i = 1; i <= slen; i++) hsh[i] = (hsh[i - 1] * p + s[i]) % mod; for (int i = 1; i <= tlen; i++) ths = (ths * p + t[i]) % mod; int ans = 0; for (int l = 1; l + tlen - 1 <= slen; l++) if (get_hash(l, l + tlen - 1) == ths) ans++; cout << ans; return 0; }

最长回文子串

例题：
反对称串

问题：给定一个$0/1$序列，求其异或意义下的回文子串的数量。

由题意得，回文子串的长度必须为偶数，否则因为对称中心一定改变，所以该子串一定不是回文子串。

我们不妨枚举它的回文中心，尽可能地扩展它的回文半径。因为回文半径具有单调性，所以考虑二分答案。至于判断回文中心两侧是否相等，可以预处理正着的 Hash 值和倒着的 Hash 值，在check函数中比较即可。代码如下：

#include <iostream> using namespace std; typedef unsigned long long ull; const int N = 1e6 + 8, p = 131; int n; string s; ull ppow[N], shs[2][N]; ull get_hash(ull h[], int l, int r) { return h[r] - h[l - 1] * ppow[r - l + 1]; } bool check(int l, int r) { return l <= r && get_hash(shs[0], l, r) == get_hash(shs[1], n - r + 1, n - l + 1); } int main() { ppow[0] = 1; for (int i = 1; i < N; i++) ppow[i] = ppow[i - 1] * p; cin >> n >> s; s = ' ' + s; for (int i = 1; i <= n; i++) { shs[0][i] = shs[0][i - 1] * p + s[i]; shs[1][i] = shs[1][i - 1] * p + (s[n - i + 1] == '0' ? '1' : '0'); // 异或的同时倒着存Hash值 } int ans = 0; for (int i = 1; i < n; i++) { int l = 1, r = min(i, n - i), mid, res = 0; // 二分答案回文半径 while (l <= r) { mid = (l + r) >> 1; if (check(i - mid + 1, i + mid)) l = mid + 1, res = mid; else r = mid - 1; } ans += res; } cout << ans; return 0; }

如果上面的二分答案只改动$l$的值为$0$，那么回文半径单峰而不单调，与二分答案要求严格单调性相违背。但若在此基础上，将$mid$向上取整，二分边界$[l, r)$左闭右开，用$l$存答案，结果仍然正确。代码如下：

int l = 0, r = min(i, n - i), mid; while (l < r) { mid = (l + r + 1) >> 1; if (check(i - mid + 1, i + mid)) l = mid; else r = mid - 1; } ans += l;

最短循环节

例题：
糟糕的诗

问题：给定一个由小写英文字母组成的长度为$L$的字符串$S$，有$q$个询问，每次询问给定$S$的一个子串，求其最短循环节。若字符串$A$能够由字符串 B 重复若干次得到，则称字符串$B$是字符串$A$的一个循环节。

仔细思考，我们能得出以下几个很重要的结论：

若$n$是循环节的长度，则$hs(l + n, r) = hs(l, r - n)$。这说明我们能够在$O(1)$的时间复杂度内判断是否为循环节。

循环节的长度$n$是总长$L$的因数。
若$n$是一个循环节的长度，$k$是循环次数，则$k \times n$也是一个循环节。这说明：先把$n$分解质因数，得到循环节的因子和循环次数的因子，从$n$开始试除总长$L$，将循环次数的因子除尽，最后得到的就是最小循环节的长度。

分解质因数用欧拉筛，时间复杂度为$O(q \sqrt L)$，常数较大加快读。代码如下：

#include <iostream> using namespace std; typedef unsigned long long ull; ull read() { ull num = 0; char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') { num = (num << 1) + (num << 3) + ch - '0'; ch = getchar(); } return num; } const int N = 5e5 + 8, p = 233; int n, q, pcnt, pri[N], mnp[N]; bool notpri[N]; string s; ull ppow[N], shs[N]; ull geths(int l, int r) { return shs[r] - shs[l - 1] * ppow[r - l + 1]; } void init() { notpri[0] = notpri[1] = true; // 欧拉筛 for (int i = 2; i < N; i++) { if (!notpri[i]) pri[++pcnt] = i, mnp[i] = i; for (int j = 1; j <= pcnt && i * pri[j] < N; j++) { mnp[pri[j] * i] = pri[j]; notpri[pri[j] * i] = true; if (i % pri[j] == 0) break; } } ppow[0] = 1; for (int i = 1; i < N; i++) ppow[i] = ppow[i - 1] * p; } bool check(int l, int r, int len) { return geths(l, r - len) == geths(l + len, r); } int main() { init(); n = read(); cin >> s; s = ' ' + s; q = read(); for (int i = 1; i <= n; i++) shs[i] = shs[i - 1] * p + s[i]; while (q--) { int l = read(), r = read(), len = r - l + 1, rmn = r - l + 1, fac; while (rmn > 1) { for (fac = mnp[rmn]; rmn > 1 && check(l, r, len / fac); fac = mnp[rmn]) { len /= fac; // len 表示循环节长度 rmn /= fac; // rmn 表示该子串剩余长度 } while (rmn > 1 && rmn % fac == 0) rmn /= fac; } cout << len << '\n'; } return 0; }

哈希表

例题：
不重复数字

问题：给定$n$个数，要求把其中重复的去掉，只保留第一次出现的数。

哈希表就是解决这个问题的数据结构。其内部采用“链地址法”解决哈希冲突。拓展一个哈希表的重要属性：负载因子$\alpha$。

\[\alpha = \frac{已有元素个数}{桶数} \]

一般认为，当$\alpha$在$0.75$左右时，哈希表的性能优秀。

代码上采用类似于链式前向星的写法封装结构体手写哈希表。事实上，STL库提供的unordered_map更为常用。

#include <iostream> #include <cstring> using namespace std; const int N = 6e4 + 8; struct hash_table { int sz, head[N], nxt[N], val[N]; int geths(int x) { return (x % N + N) % N; } void init() { sz = 0; memset(head, 0, sizeof(head)); } int find(int x) { int h = geths(x); for (int i = head[h]; i; i = nxt[i]) if (val[i] == x) return i; return 0; } int insert(int x) { if (find(x)) return 0; int h = geths(x); nxt[++sz] = head[h]; val[sz] = x; head[h] = sz; return sz; } } ht; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T, n; cin >> T; while (T--) { cin >> n; ht.init(); for (int i = 1, x; i <= n; i++) { cin >> x; if (ht.insert(x)) cout << x << ' '; } cout << '\n'; } return 0; }

确定字符串中子字符串的个数

例题：
Beads 项链

问题：给定长为$n$的序列，将它划分为每段长度都为$k$的子串，求最多可以得到的不同子串的个数、取到最优解时不同的$k$值和$k$的个数。子串可反转。

正向、反向做两遍 Hash 求子串的 Hash 值。利用set数据结构自动去重。每次选择 Hash 值更小（大）的情况插入即可。代码如下。

#include <iostream> #include <set> #include <vector> using namespace std; typedef unsigned long long ull; const int N = 2e5 + 8, p = 233333; ull hs[2][N], ppow[N]; int n, a[N]; ull geths(ull h[], int l, int r) { return h[r] - h[l - 1] * ppow[r - l + 1]; } int main() { ppow[0] = 1; for (int i = 1; i < N; i++) ppow[i] = ppow[i - 1] * p; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { // 正向、反向 Hash hs[0][i] = hs[0][i - 1] * p + a[i]; hs[1][i] = hs[1][i - 1] * p + a[n - i + 1]; } int ans = 0; vector<int> dk; for (int k = 1; k <= n; k++) { if (n / k < ans) break; // 最优性特判 set<ull> st; // 自动去重 for (int l = 1; l + k - 1 <= n; l += k) { // r = l + k - 1 int h1 = geths(hs[0], l, l + k - 1), h2 = geths(hs[1], n - l - k + 2, n - l + 1); st.insert(min(h1, h2)); // 统一选择 Hash 值更小的子串 } if (st.size() > ans) { dk.clear(); dk.push_back(k); ans = st.size(); } else if (st.size() == ans) dk.push_back(k); } cout << ans << ' ' << dk.size() << '\n'; for (int k : dk) cout << k << ' '; return 0; }