P3370 【模板】字符串哈希 题解

· · 题解

我们定义一个把字符串映射到整数的函数 f，称其为 Hash 函数。

我们希望该函数能帮助我们快速判断两个字符串是否相等。根据此目标，我们希望该函数满足：

但在绝大多数情况下，当 Hash 函数值相同时，我们不能保证两个字符串相同，只能使两个字符串大概率相同。我们将 Hash 函数值相同但原字符串不同的现象称为 Hash 冲突或 Hash 碰撞。

通常情况下，我们采用的是下面的定义方法：

f(s)=\left(\sum_{i=1}^n s_i \times b^{n-i} \right) \bmod M

其中，b 通常是一个不小于 |\Sigma| 的整数，我们称其为底数；M 是一个大整数，我们称其为模数。可以将其类比为一个 b 进制数理解，对 M 取模是为了避免返回值太大导致无法比较。

接下来，我们考虑出现 Hash 冲突的概率。

我们设模数为 M，需要计算的字符串的数量为 n，则出现 Hash 冲突的概率为：

P(n,M)=1-\prod_{i=0}^{n-1} \dfrac {M-i}{M}=1-\dfrac{M!}{M^n(M-n)!} \approx 1-\exp\left(-\dfrac {n(n-1)}{2M}\right)

具体证明可以参考 OI Wiki。

通常情况下，当 n 是 \mathcal O(\sqrt M) 量级的时候，出现 Hash 冲突的概率就很大了。

我们可以使用 unsigned long long 来定义 Hash 函数的结果，相当于把模数 M 设置为 2^{64}。这种方法被称作自然溢出，在随机数据下出现 Hash 碰撞的概率很低，但容易被刻意构造的数据卡住。

我们还可以使用多模 Hash，即定义多个模数 M 不同的 Hash 函数。判断时，只要有其中一个 Hash 函数值不同就认为两个字符串不同，当且仅当所有 Hash 函数值相同时才认为两个字符串相同。通常情况下，双模 Hash 就够用了。

以上知识对于解决本题已经够用了，接下来我们来看一些常用的拓展知识。

我们考虑怎么优化该算法的时间复杂度。

当题目需要多次查询子串的 Hash 函数值时，我们可以做到 \mathcal O(n) 预处理，\mathcal O(1) 回答单次询问。

具体而言，对于字符串 s，我们定义 v_i 表示 f(pre_i)，即 s 的长度为 i 的前缀的 Hash 函数值。根据定义，我们有：

\begin{aligned} v_i&=\left(\sum_{j=1}^i s_j \times b^{i-j} \right) \bmod M\\ &=\left(s_i+\sum_{j=1}^{i-1} s_j \times b^{i-j}\right)\bmod M\\ &=\left(s_i+\left(\sum_{j=1}^{i-1} s_j \times b^{i-1-j}\right)\times b\right)\bmod M\\ &=\left(s_i+v_{i-1} \times b\right)\bmod M\\ \end{aligned}

其中我们认为 v_0=0。

对于 s[l,r]，我们考虑用类似前缀和的方式计算它的 Hash 函数值：

\begin{aligned} f(s[l,r])&=\left(\sum_{i=l}^{r} s_i \times b^{r-i}\right) \bmod M \\ &=\left(\sum_{i=1}^r s_i \times b^{r-i}- \sum_{i=1}^{l-1} s_i \times b^{r-i}\right) \bmod M\\ &=\left(\sum_{i=1}^r s_i \times b^{r-i}- \left(\sum_{i=1}^{l-1} s_i \times b^{l-1-i}\right) \times b^{r-l+1}\right) \bmod M\\ &=\left(v_r-v_{l-1} \times b^{r-l+1}\right) \bmod M \end{aligned} 字符串 Hash 题单链接：<https://www.luogu.com.cn/training/682394> 字符串 Hash 题单题解链接：<https://www.luogu.com.cn/article/gze8zzs2>