字符串哈希

字符串

发布日期: 2022-06-20

更新日期: 2022-06-20

文章字数: 769

阅读时长: 3 分

哈希是一种映射方法，我们用哈希把万物映射成一个整数值，字符串哈希就是把字符串映射为一个整数值，这样我们就能快速判断两个字符串是否相同。字母集$T$就是我们用到所有字母的集合，$|T|$就是其大小。$H$为哈希函数,$S$为字符串，$n$为其长度，$H(S)$即为字符串$S$的哈希值，$mod$是模数

字符串哈希最常用的方法就是把整个字符串当成一个$K$进制数，其中$K\ge |T|$，而我们遇到的题目中一般都满足$|T|\le 128$，我们可以选择$K=131、137$等等数值，最好是质数，因为我们计算的时候整数的值过大，我们需要取模。

按照这种方法，假设有字符串$S$，且其下标从1开始，那么$H(S)=\sum_{i=1}^{n}S[i]\times K^{n-i+1}$，这个值过大，我们需要取模，模数肯定也要选择比较大的质数，模数小会很容易出现冲突，即两个并不相同的字符串哈希值相同，我们可以取$mod=1e9+7、1e9+9、1610612741$，其中第三个是比较好的哈希模数。（因为前两个用的太多了，出题人更容易卡我们）但是就算如此，当我们需要检测的次数特别多时，我们还是很容易出错，因此我们可以用不同的$K$和$mod$算两个哈希值，这样出错概率就会大大降低。

另外，根据生日悖论，我们使用的模数最好大于等于检测次数的平方。

子串哈希

由上面的内容，我们很容易知道$H(S[l\sim r])=(S[l]\times K^{r-l}+\cdots + S[r])%mod$。

假设我们令$F[i]=H(S[1\sim i])$，那么有

$F[l-1]=(S[1]\times K^{l-2}+S[2]\times K^{l-3}+\cdots+S[l-1])%mod$

$F[r]=(S[1]\times K^{r-1}+S[2]\times K^{r-2}+\cdots +S[r])%mod$

我们易知$H(S[l\sim r])=F[r]-F[l]\times K^{r-l+1}$

因此我们只要求出$S$对应的$F$，就能快速求出其子串的哈希。

而我们也易得$F[i+1]=F[i]\times K+S[i+1]$

另外，如果给我们$H(S[l_{1}\sim r_{1}])$和$H(S[l_{2}\sim r_{2}])$那么我们可以快速得到这两个字串拼接起来后得到的字符串的哈希值为$H(S[l_{1}\sim r_{1}])\times K^{r_{2}-l_{2}+1}+H(S[l_{2}\sim r_{2}])$，由此我们想到如果我们要修改字符串的话，我们就可以用线段树来维护字符串的哈希值了！