关于字符串哈希

百步穿杨 · 2023-06-06 22:18:22 · 个人记录

字符串哈希还是很好用的 可以水掉一些KMP的题

字符串哈希和数字哈希经常是一起用的

思路核心是通过一个固定的base进制来将字符串处理为哈希值，每一位的数字就是他的ASCII码

一些注意的点：

关于base的取值，一般都会选用131，13331这种数字，但我看来只要大于ASCII码的最大值就行，已经能够很好地处理冲突。不必纠结

冲突主要发生于两个不同字符串拥有相同哈希，base值太小就容易导致，大一些冲突的几率会减小

代码实现

1. 求母串的哈希数组

for(int j=1;j<=s.size();j++){
    Hs[j]=Hs[j-1]*p+s[j-1]-'A';
}
//p是base值，Hs[]是前缀和数组，用处后面说

2. 求子串的哈希值

for(int j=1;j<=s1.size();j++){
    g=g*p+s1[j-1]-'A';
}

与求母串的做法相同，只是不需要处理前缀数组，得到一个值即可。

3. 匹配

匹配的核心是如何把母串中每一个子串的哈希值处理出来

利用前缀和的性质处理出母串每一个字串的哈希值

for(int j=s1.size();j<=s.size();j++){
    unsigned long long s=Hs[j]-Hs[j-s1.size()]*pw[s1.size()];
   //unsigned long long 是为了让值自然溢出，作用相当于取模
   //pw[]是预处理的p的n次方
    if(s==g){
        num++;
    }
   //若相等，字串数++
}