字符串 - 哈希 | 喵喵小窝

定义

对于字符串 $S$ ，一般来说哈希方法是，我们把它看作一个 $B$ 进制数对质数 $P$ 取模，具体地说：

$F(S)\equiv \sum_{i=1}^{|S|}B^{|S|-i}S_i\pmod P$

为什么要这样？好处是，我们可以递推求出前缀的哈希，即 $F(S[1,i])\equiv F(S[1,i-1])B+S_i\pmod P$ 。

此外，还有 $F(S[l,r])\equiv F(S[1,r])-F(S[1,l-1])B^{r-l+1}\pmod P$ 。

我们通过一个题目来看模数怎么选。

按照我们的理论，随机一个字符串等价于随机一个 $B$ 进制数，当然其中的 $S_i$ 是 $[1,26]$ 内取的。

那么这样对 $P$ 取模，就等价于一个随机数对 $P$ 取模。

根据生日悖论， $O(\sqrt P)$ 次会出现两个值取模后相等。

注意是存在两个相等的，而不是对一个已经固定的数相等，所以我们用一个 map 记录，这样复杂度是 $O(\sqrt{P}\log P)$ 。

由这个题目我们可以知道，只要让自己选的模数 $P$ 比检测次数的平方高几个数量级，就是安全的。

首先转化为询问 $a_l\sim a_r$ 中，奇数位置元素构成的多重集，与偶数位置构成的多重集是否相同。

那么对于两个序列的比较，想到哈希是不难的，问题是这道题目还有区间加的操作，我们应该如何哈希。

假设我们已经有了一个针对集合的哈希函数 $F(S)$ ，那么对于一个多重集 $A=\{a_1,a_2,\dots,a_k\}$ ，下面会是一个容易想到的设计：

$F(A)=\sum_{i=1}^k f(a_i)$

也许读者会思考，为什么这里不和字符串哈希那样，把字符串当成一个 $P$ 进制数？这是因为我们设计的是集合的哈希，而集合是无序的，而利用加法的交换率设计哈希函数正好可以满足集合的无序这个特点。

那么接下来考虑更新，即思考如何完成区间加 $v$ 这一操作。

$F(A)\gets \sum_{i=1}^k f(a_i+v)$

我在 VP 时会想把 $f(x)$ 设计为一个多项式函数，即 $f(x)\equiv ax^3+bx^2+cx+d\pmod p$ ，其中 $p$ 是一个自己选定的质数。这确实可行，下面我来讨论一下为什么这样不是很好。

首先我们希望减少哈希碰撞。但是当 $\sum x^2\neq \sum y^2$ 、 $\sum x^3\neq \sum y^3$ 时， $a\sum x^3+b\sum x^2=a\sum y^3+b\sum y^2$ 是有可能成立的，所以这个设计不如分别比较平方和与立方和。

而平方和与立方和给我们的操作空间就很小了，因为你选定的参数 $a,b,c,d$ 实际上是无效的，那么我们唯一有效的就是那个质数 $p$ 了。

然而，如果将 $f(x)$ 设计为指数函数，即 $f(x)\equiv a^x\pmod p$ ，这里的 $a,p$ 参数是我们随便选择的，碰撞的概率会更小，并且区间加也只是区间的哈希值乘 $a^v$ ，维护也更加便捷。

我这里给出我的赛时代码，是比较 $\sum x^3$ 的，仅供参考。

这个题对于 $l,r$ 奇偶的讨论也很烦人，并且由于更新时并不保证 $l,r$ 长度为偶数，所以很有可能存在这个更新只更新了一个数字，而这就导致我们更新的时候需要特判一下是不是会 $l>r$ ，否则会 Runtime error on test 12。