字符串哈希

Keywords: #algorithm

字符串哈希,是一种能将字符串映射成非负整数的算法.

一般使用BKDR Hash进行哈希计算.

具体做法是,将字符串看作一个 $b$ 进制的数字,计算它在十进制下的数值.

由于在字符串足够长时数字会过大,因此一般会取模一个大质数.

参考代码(只包含a-z的字符串):

const int mod=1e9+7,b=27;
int getstrhash(string str){
    int len=str.size();
    int ans=0;
    for(int i=0;i<len;i++){
        ans=((long long)ans*b+(str[i]-'a'+1))%mod;
    }
    return ans;
}

注意:如果使用上面的做法,注意是str[i]-'a'+1,否则aab和ab的哈希值相同.

上面这种方法因为在实际使用时涉及到大量取模操作,所以通常利用unsigned long long类型溢出自动取模 $2^{64}-1$的性质,使用下面这种方法:

const int b=27;
unsigned long long getstrhash(string str){
    int len=str.size();
    unsigned long long ans=0;
    for(int i=0;i<len;i++){
        ans=ans*b+(str[i]-'a'+1);
    }
    return ans;
}

求子串哈希

如果要计算子串哈希(比较子串是否相等),直接暴力计算,单次查询 $O(n)$ 复杂度.

使用类似前缀和的思想可以优化此过程.

具体做法是,预处理字符串(假设为str)的每个前缀哈希,利用求哈希时将字符串看作一个 $b$ 进制数的特点,将哈希值"左移"后相减.

例子:给定字符串 $s=“abb”$,求 $“bb”$ 的哈希值.

预处理出前缀哈希值

$pre[0]=1*27^0=1$

$pre[1]=1*27^1+2*27^0=29$

$pre[2]=1*27^2+2*27^1+2*27^0=785 $

然后结果为$pre[2]-pre[0]*27^2$.

参考代码

int getsubstrhash(int l,int r){
    return pre[r]-pre[l-1]*powofbase[r-l+1];
    //powofbase[i]为b的i次方
}
← prev