字符串的hash

约 210 个字 49 行代码 预计阅读时间 1 分钟

字符串映射为整数，$O(1)$ 比较字符串

原理

$hash=\sum\limits_{i=1}^n base^{n-i}a_i$

把字符串看成 $base$ 进制数，并模一个大数解决溢出

$0<a_i<base<mod,gcd(base,mod)=1$

例如把只有小写字母的字符串的 $a_i$设为 $s_i-'a'+1$

这些限制都是为了减少冲突可能性

base可以取131或13331，冲突小

大数不可以取 $2^{64}$ （即ull自然溢出），因为会被卡掉

大数最好用大质数，可以取1e9+9

或者使用双模数（即使用两个模数对一个字符串计算两遍哈希值，根据中国剩余定理，这可以使哈希范围扩大到两数乘积

当然可以类似的使用更多模数

typedef unsigned long long ull;
const int N=1e6+1,modnum=2;
const ull base=131,mod[modnum]={(ull)1e8+7,(ull)1e9+9};
ull pw[modnum][N];
void init()
{
    for(int j=0;j<modnum;++j)
    {
        pw[j][0]=1;
        for(int i=1;i<N;++i)
            pw[j][i]=pw[j][i-1]*base%mod[j];
    }
}
void initHash(string &s,vector<vector<int>> &h)
{
    h.resize(modnum);
    for(int j=0;j<modnum;++j)
    {
        h[j].resize(s.size()+1);
        h[j][0]=0;
        for(int i=0;i<s.size();++i)
            h[j][i+1]=(h[j][i]*base+s[i]-'a'+1)%mod[j];
    }
}
array<ull,modnum> subHash(vector<vector<int>> &h,int l,int r)
{
    array<ull,modnum> res;
    for(int i=0;i<modnum;++i)
        res[i]=(h[i][r]+mod[i]-h[i][l-1]*pw[i][r-l+1]%mod[i])%mod[i];
    return res;
}

判断回文串

原哈希值和reverse哈希值一样

void initHash(string &s,vector<vector<int>> &rev)
{
    rev.resize(modnum);
    for(int j=0;j<modnum;++j)
    {
        rev[j].resize(s.size()+1);
        rev[j][0]=0;
        for(int i=0;i<s.size();++i)
            rev[j][i+1]=(rev[j][i]*base+s[s.size()-1-i]-'a'+1)%mod[j];
    }
}
array<ull,modnum> subHash(vector<vector<int>> &rev,int l,int r)
{
    array<ull,modnum> res;
    for(int i=0;i<modnum;++i)
        res[i]=(rev[i][rev[0].size()-l]+mod[i]-rev[i][rev[0].size()-1-r]*pw[i][r-l+1]%mod[i])%mod[i];
    return res;
}