字符串Hash
我们定义一个把字符串映射到整数的函数 \(f\) ，这个 \(f\) 称为是 \(Hash\) 数。
我们希望这个函数 \(f\) 可以方便地帮我们判断两个字符串是否相等。
基础公式：
$f(s)= {\textstyle \sum_{i=1}^{l}} s[i] \times b^{l-i} $ \((mod\) \(m)\)**
哈希冲突
指在一定模数下，两个不同的字符串映射到相同\(Hash\)值。
我们设 \(Hash\) 的取值空间（所有可能出现的字符串的数量）为\(d\)，计算次数（要计算的字符串数量）为\(n\)。
则 \(Hash\) 冲突的概率为：
\(p(n,d)=1-\frac{d!}{d^n(d-n)!}\approx 1-exp(-\frac{n(n-1)}{2d})\)
赛场常用技巧
-
自然溢出：使用\(unsigned\) \(long\) \(long\)定义\(Hash\)值变量，此时模数为\(2^{64}\)，优点是方便、代码简单，缺点是极其容易被卡，详见oi-wiki。
-
双值\(Hash\)：同时使用两种不同模数求出一个字符串的\(Hash\)值。当两个字符串相同时，两值必定都相同。优点是不容易被卡、应对赛场环境足以，缺点是代码复杂。
-
多次询问\(Hash\)值：令\(f_i(s)\)表示字符串\(s\)的长度为\(i\)的前缀的\(Hash\)值，可以得到\(f(s[l..r])=f_r(s)-f_{l-1}(s)\times b^{r-l+1}\)成立。
-
二分求最长公共子字符串
常用\(Hash\)值
-
998244353
-
1000000007
-
19260817
-
自然溢出