字符串基础

字符串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})\)

赛场常用技巧

1. 自然溢出：使用\(unsigned\) \(long\) \(long\)定义\(Hash\)值变量，此时模数为\(2^{64}\)，优点是方便、代码简单，缺点是极其容易被卡，详见oi-wiki。

2. 双值\(Hash\)：同时使用两种不同模数求出一个字符串的\(Hash\)值。当两个字符串相同时，两值必定都相同。优点是不容易被卡、应对赛场环境足以，缺点是代码复杂。

3. 多次询问\(Hash\)值：令\(f_i(s)\)表示字符串\(s\)的长度为\(i\)的前缀的\(Hash\)值，可以得到\(f(s[l..r])=f_r(s)-f_{l-1}(s)\times b^{r-l+1}\)成立。

4. 二分求最长公共子字符串

常用\(Hash\)值

1. 998244353

2. 1000000007

3. 19260817

4. 自然溢出