字符串 Hash
定义把一个字符串映射到整数的函数 $f$，这个 $f$ 称为是 Hash 函数。
通过这个映射可以判断两个字符串是否相等。
attention：
注意区分哈希和字符串哈希，字符串哈希是哈希问题的一个子集。哈希的另一个经典应用为哈希表。本文介绍字符串哈希。
进制哈希（多项式哈希）：
将字符串视作一个 $|c|$ 进制数（$|c|$ 表示字符集大小），计算得到的结果即为 $f$ 的值。
优点：
- 唯一确定，不会产生任何哈希冲突。
- 每一位字符独立。比如修改字符串中的某一个字符，只需要加减对应权值即可。
缺点：
- 值域过大，映射的值与字符串长度呈强相关，在字符串长度较长时，存不下这么大的值。
多项式模数哈希（模哈）：
即在多项式哈希的基础上，对最后的结果取模。
优点：
- 可以将字符串映射到 $[0,\bmod)$ 中，方便存储。
- 模运算具有优秀的性质，可以支持很多其它操作（比如修改字符串中的某一个字符，只需要加减取模即可）。
缺点：
- 映射范围较小容易产生哈希冲突。
多项式哈希冲突概率：
设模数为 $\bmod$，则映射集合为 $[0,\bmod-1]$。
假设字符串随机分布，即哈希值随机分布（每次从 $[0,\bmod-1]$ 中随机选一个数）。
根据“生日悖论”，在随机 $\sqrt{\bmod}$ 次后，有约 $\dfrac{1}{2}$ 的概率产生冲突。
若产生冲突，则字符串哈希用于“判断两个字符串是否相同”的目的即失效。
所以在随机情况下，$\bmod$ 一般要超过 $\sqrt{\text{字符串数目}}$。
但是上述结论建立在随机的情况下，在实际场景中，往往可以通过对特定模数的特定构造，达到 $2$ 次即冲突的情况。
双模数多项式哈希（双模哈）：
即使用两个模数，分别进行多项式模数哈希，只有在两者结果均相同时，认为字符串相同。
同样考虑随机分布下，在随机 $\bmod$ 次后，有约 $\dfrac12$ 的概率产生冲突。
但是这并不能改变哈希冲突的可能性。
构造哈希冲突：
前文中的“生日悖论”概率建立在随机分布意义下，但是由于取模运算本身的性质，哈希冲突并不完全是随机分布的。
考虑：$a\equiv x\pmod c$。
冲突的情况即为同余方程解的数目。
$a\equiv x\pmod c\Leftrightarrow x=a+yc $
若 $\gcd(a,c)\neq 1$，令 $k=\gcd(a,c)$，则 $x=ka’+ykc’\rightarrow \frac{x}{k}=a’+yc’$，即：解空间由 $\lbrace x\rbrace$ 变成了 $\lbrace\dfrac{x}{k}\rbrace$，若原本的冲突空间为 $[0,\bmod-1]$，此时则为 $[0,\dfrac{\bmod-1}{k}]$。
那么为了使冲突空间尽可能大，就要使 $\gcd(a,c)$ 尽可能小，直接让 $\gcd(a,c)=1$ 即可，所以通常选取一个大质数作为模数。
应用：
求一个子串的哈希值：
因为本质上多项式哈希是给每一位字符一个权值然后全部加起来。那么对于一个区间 $[l,r]$ 的权值和，维护一个差分前缀和即可。
一个注意的点是：差分直接得到的是原串中的权值和，并不是一个新的字符串的哈希值（位的权值不一样）。要视作一个新的字符串，则要将权值和除以 ${|c|}^{l}$ 即可。
字符串匹配：
直接判断哈希值是否相等即可。
最长回文子串：
引理：若子串 $sl,r$ 为回文串，则 $s[l-1,r-1]$ 也为回文串。
由引理可得，以回文串中点开始，回文串半径长度满足单调性。
所以可以枚举回文串中点，后二分半径长度，判断左右两部分是否一致即可。
因为左右两部分顺序相反，所以需要对原字符串顺着做一遍哈希后逆着再做一遍哈希。
最长公共前缀（LCP）：
最长公共前缀显然也是满足二分性的，所以二分长度后哈希判断是否相同即可。
本质不同回文子串：
一个字符串的本质不同回文子串规模为 $O(n)$（一个容易的证明是回文自动机（PAM）共有 $n$ 个节点）。所以可以使用字符串哈希将所有本质不同的回文子串存下来。
具体方法是：枚举回文串中点时，二分找到最长半径后暴力不断缩小半径，直到遇到出现过的回文子串后终止。