当前位置：首页 > news >正文

字符串哈希

news 来源：原创 2024/5/8 12:06:11

hash函数

设字符集大小为 $B$ ，将所有字符编号为 $0, 1, . . ., B - 1$ ，则一个串可以看做一个 $B$ 进制数，以 $B$ 进制展开计算一个长 $m$ 的串 $t$ 的 $h a s h$ 值， $P$ 是一个大质数，减少碰撞次数

$Hash(t)=\sum_{i=0}^{m-1}{ t_i·B^{m-i+1}~mod~P}$

单模数哈希

ull base=131;
int prime=233317;
ull mod=212370440130137957LL;

ull hash(char *s){
    int len=strlen(s);
    ull ans=0;
    for(int i=0;i<len;i++)
    	ans=(ans*base+(ull)s[i])%mod+prime;
    return ans;
}

自然溢出哈希

根据 $u s i g n e d l o n g l o n g$ 自然溢出的性质优化（溢出自动取模）

ull base=131;

ull hash(char *s){
    int len=strlen(s);
    ull ans=0;
    for(int i=0;i<len;i++)
    	ans=ans*base+(ull)s[i];
    return ans;
}

双哈希

更安全的做法是双哈希，翻车几率更低

ull base=131;
ull mod1=19260817,mod2=19660813;

ull hash1(char *s){
    int len=strlen(s);
    ull ans=0;
    for(int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod1;
    return ans;
}

ull hash2(char *s){
    int len=strlen(s);
    ull ans=0;
    for(int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod2;
    return ans;
}

hash函数的滚动性质

设 $H (s, l, r)$ 为串 $s$ 的子串 $s_ls_{l+1}...s_r$ 的 $h a s h$ 值，则：

$H(s,l+1,r+1)=(H(s,l,r)-s_lB^{r-l})·B+S_{r+1}$
在这里插入图片描述
例如找串 $s$ 中是否包含子串 $t$ ：

利用滚动性质，先 $O (m)$ 求出模式串 $t$ 的 $h a s h$ 值，然后 $O (n)$ 扫一遍文本串 $s$ 所有长 $m$ 的子串的 $h a s h$ 值，就可以找出匹配

ull base=131;

int rabin_karp(char *t,char *s){
    int n=strlen(s),m=strlen(t);
    if(n<m) return -1;
    ull bn=1;
    for(int i=0;i<m-1;i++) bn=bn*base;
    ull key=0,cur=0;
    for(int i=0;i<m;i++){
        key=key*base+(t[i]-'a');
        cur=cur*base+(s[i]-'a');
    }
    for(int i=0;i<n-m+1;i++){
        if(cur==key) return i;
        cur=cur-bn*(s[i]-'a');
        cur=cur*base+(s[i+m]-'a');
    }
    return -1;
}

动态维护子串hash

区间的 $h a s h$ 是可合并的，即如果知道了 $H (s, l, m i d)$ 和 $H (s, m i d + 1, r)$ ，则：

$H(s,l,r)=(H(s,l,mid)*B^{r-mid}+H(s,mid+1,r))~mod~P$

问题引入

维护子串的 $h a s h$ 值，有两种操作：

单点修改：可以将 $s$ 的某个字符修改为 $c$
区间查询：查询 $s$ 的子串 $s_ls_{l+1}...s_r$ 的 $h a s h$ 值

ull base=131;

char s[maxn];
ull sgt[maxn*4],bn[maxn]; //bn[i]=base^i

void build(int i,int l,int r){
    if(l==r){
        sgt[i]=s[l]-'a';
        return;
    }
    int mid=(l+r)>>1,k=i<<1;
    build(k,l,mid);
    build(k|1,mid+1,r);
    sgt[i]=sgt[k]*bn[r-mid]+sgt[k|1];
}

ull query(int i,int l,int r,int x,int y){
    if(x<l || y<r) return 0;
    if(x<=l && y<=r) return sgt[i];
    int mid=(l+r)>>1,k=i<<1;
    int len=max(0,max(r,y)-max(mid+1,x)+1);
    return query(k,l,mid,x,y)*bn[len]+query(k|1,mid+1,r,x,y);
}

void modify(int i,int l,int r,int pos,char x){
    if(l==r){
        sgt[i]=x-'a';
        return;
    }
    int mid=(l+r)>>1,k=i<<1;
    if(pos<=mid) modify(k,l,mid,pos,x);
    else modify(k|1,mid+1,r,pos,x);
    sgt[i]=sgt[k]*bn[r-mid]+sgt[k|1];
}