字符串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
-
自然溢出