前排提示，字符串哈希所需要的数理算力、代码能力都不低。但本质很基础。
面对非“树上、图上字符串问题”：
一方面：字符串 hash 的在任何一个模型上都不是理论最优解。大常数致使几乎只能达到 \(5 \times 10^{5}\) 每秒。
另一方面：字符串 hash 的通用性、相对优性、相对易性，意味着它是实际思路下的最优解。更复杂的情况留给后续优化。
这篇文章将会让字符串 hash 以稍坏的复杂度完成：
- 模式串匹配算法：替代 KMP 算法、Z 算法
- 回文串算法：替代 manacher
- 循环表示算法：替代 最小表示法
- 最长公共前缀算法：替代线性 lcp 算法
- 特殊性质：
- 常数失配匹配
- 回文信息合并
- 对朴素暴力的优化性质：
- 优化 string 作为 map 键值
- 本质不同子串数量
- 最长公共子串
一 字符串 hash 与 模式串匹配
1.1 hash 公式、系数、模数
对一个字符串 \(s\) ，不妨把字符权值视为它的 \(ascii\) 码，第 \(i\) 个字符权值令为 \(c_i\) 。考虑一个前缀的 hash 的表现形式： \(ha(x) = \sum_{i = 1}^{x} c_i b^{x - i}\) 。
模数：
显然需要在模意义下进行，通常取一个质数 \(p\) ：选取质数的其中一个好处是 \(a \times k \bmod m\) 的落点间距是 \(gcd(a, m)\) 。
通常选取 $1e9 \sim 2e9 $ 之间的 \(p\) ，好处是 \(p\) 在 \(int\) 内，且 \(p^{2}\) 在 \(long\ long\) 内。
有素数定理，可以选 \(x \in [10^{9}, 2 \times 10^{9}]\) ，然后暴力往后找一个素数。朴素算法大概可以在几秒内完成。
系数：
系数的选取一般只需要大于字符集，小于模数即可。
1.2 multi hash
经验上，负载因子 \(\alpha\) 大时，hash 几乎没有冲突率。公式 hash 一旦冲突会误判相等（但不会误判不等）。
可以对 hash 公式更换系数 \(b\) 和模数 \(p\) 得到其他公式。多个公式得到的 hash 值同时相等才认为相等，使冲突率可以更低。
1.3 用于模式串匹配的字符串 hash
综合上述原因，字符串哈希可以表达成：
\[ha_{h, x} = (\sum_{i = 1}^{x} ha_{h, i - 1} \times base_{h}^{x - i} + c_{x}) \bmod p_{h} \]第 \(h\) 重哈希，考虑到前缀 \(x\) ，系数是 \(base_h\) ，模数是 \(p_{h}\) 。
再进一步，将多重 hash 的数组封装成一个类（容器会很慢并且不够面向对象），重载构造函数和等号。于是可以方便地调用多重 hash 值。
1.4 子串哈希值
由于 hash 公式是下降幂的形式，让 \(l\) 的前缀 hash 进行补幂后，被 \(r\) 的前缀 hash 减去。
\[\begin{aligned} ha_{l, r} &= (\sum_{i = 1}^{r} c_i \times base^{i} - \sum_{i = 1}^{l - 1} c_i \times base^{i} \times base^{r - l}) \bmod p \\ &= (ha_r - ha_l \times base^{r - l}) \bmod p \\ \end{aligned} \]1.5 模式串匹配的常见模型
1.5.1 平凡模式串匹配
平凡模式串匹配：给一个文本串 \(text\) 和一个模式串 \(pattern\) ，询问 \(pattren\) 在 \(text\) 中出现过多少次。
根据 1.1 - 1.4 的述描述，可以写出伪代码：
function solve(text, pattern):
cnt = 0
ha1 = get_hash(text)
ha2 = get_hash(pattern)
for i : 1 to n - m + 1:
if ha1.subhash(i, i + m - 1) == ha2:
cnt += 1
return cnt
参考列题：http://oj.daimayuan.top/course/22/problem/908