字符串哈希

Vision271 · 2022-07-19 10:03:15 · 个人记录

字符串哈希

进制哈希

• 进制哈希通过把字符串转换成一个字符值域上限进制的数并哈希来快速地比对字符串是否相同。

• 作用、实现见上，复杂度 O(len)。

• 通常会使用双模数防卡(字符串的进制太大了。指望拉链表似乎不太可能)。

• 实际上，双模数还是能卡的（CF 有人干过），但三模数想卡就需要很久的时间（生成对应大数），然而三模数的常数根本不能接受。好消息是：除了 CF 之外你基本不用担心被卡。

struct hseds{
    ll v1,v2;
    hseds(){}
    hseds(ll _v1,ll _v2){v1=_v1,v2=_v2;}
    bool operator<(const hseds b) const{return v1!=b.v1?v1<b.v1:v2<b.v2;}
};

hseds strhash(string &sn){
    ll v1n=0,v2n=0,len=sn.size();
    For(i,0,len-1) v1n=(v1n*pow1%mod1+sn[i])%mod1;
    For(i,0,len-1) v2n=(v2n*pow2%mod2+sn[i])%mod2;
    return hseds(v1n,v2n);
}

差分求子串(个人叫法)

• 差分求子串通过对位权的变换来实现子串的平移，从而快速地求任意子串的哈希值。

• 实现原理：

  • 仔细考察上面的过程。很像快读对吧?毕竟是秦九韶算法。
  • 将子串左侧的哈希值平移!
  • 举个例子。 l,r 。 v[s[l\dots r]]=v[s[0\dots r]]-v[s[0\dots l-1]]* pow^{r-l+1} 。

hseds subhseds(int l,int r,hseds rs[]){
    hseds ret;
    ret.v1=(rs[r].v1-rs[l-1].v1*p1[r-l+1]%mod1+mod1)%mod1;
    ret.v2=(rs[r].v2-rs[l-1].v2*p2[r-l+1]%mod2+mod2)%mod2;
    return ret;
}