字符串哈希

引入

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

从定义可以看出，字符串 Hash 函数的实质是：把每个不同的字符串转化为不同的整数，希望 \(O(1)\) 判断两个字符串是否相等。
然而事实上，经常会出现两个不同的字符串映射到相同的 Hash 值的现象，称为 哈希冲突。由此引出哈希函数两条最重要的性质。

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

对于一个长度为 \(l\) 的字符串 \(s\)，定义其多项式 Hash 函数为：$$f(s) = \sum_{i=1}^l s \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 码，用数组预处理基数的幂。
自然溢出法

顾名思义，利用无符号长整形 unsigned long long自然溢出的特性。若数据超出 ull 的存储范围，则结果自然 \(\pmod {2^{64}}-1\)。Hash 公式如下：

1. typedef unsigned long long ull;
2. ull hs[N];
3. 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)\)。代码如下：

1. #include <iostream>
2. #include <map>
3. using namespace std;
4. typedef unsigned long long ull;
5. const int N = 2e4 + 8, p = 233;
6. ull ppow[N], hs[N];
7. int n, k, a[N];
8. ull geths(int l, int r) {
9.     return hs[r] - hs[l - 1] * ppow[r - l + 1];
10. }
11. bool check(int mid) {
12.     map<ull, ull> mp;
13.     for (int l = 1; l + mid - 1 <= n; l++) {
14.         ull h = geths(l, l + mid - 1);
15.         if (++mp[h] >= k) return true;
16.     }
17.     return false;
18. }
19. int main() {
20.     ppow[0] = 1;
21.     for (int i = 1; i < N; i++) ppow[i] = ppow[i - 1] * p;
22.     cin >> n >> k;
23.     for (int i = 1; i <= n; i++) {
24.         cin >> a[i];
25.         hs[i] = hs[i - 1] * p + a[i];
26.     }
27.     int l = 0, r = n, mid, ans;
28.     while (l <= r) {
29.         int mid = l + r >> 1;
30.         if (check(mid)) l = mid + 1, ans = mid;
31.         else r = mid - 1;
32.     }
33.     cout << ans;
34.     return 0;
35. }

复制代码

最短循环节

例题：
糟糕的诗

问题：给定一个由小写英文字母组成的长度为 \(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)\)，常数较大加快读。代码如下：
[code]#include 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  1 && rmn % fac == 0) rmn /= fac;        }        cout  T;    while (T--) {        cin >> n;        ht.init();        for (int i = 1, x; i > x;            if (ht.insert(x)) cout  a;    for (int i = 1; i

感谢分享

这个好，看起来很实用

这个有用。

收藏一下   不知道什么时候能用到

新版吗？好像是停更了吧。

新版吗？好像是停更了吧。

东西不错很实用谢谢分享