本文共 2476 字，大约阅读时间需要 8 分钟。

hash函数

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

$Hash(t)={\sum }_{i=0}^{m-1}{t}_i\cdot B^{m-i+1}modP$

单模数哈希

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

自然溢出哈希

根据$usignedlonglong$自然溢出的性质优化（溢出自动取模）

ull base=131;ull hash(char *s){       int len=strlen(s);    ull ans=0;    for(int i=0;i

双哈希

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

ull base=131;ull mod1=19260817,mod2=19660813;ull hash1(char *s){       int len=strlen(s);    ull ans=0;    for(int i=0;i

hash函数的滚动性质

设$H(s,l,r)$为串$s$的子串$s_l{s}_{l+1}...s_r$的$hash$值，则：

$H(s,l+1,r+1)=(H(s,l,r)-s_l{B}^{r-l})\cdot B+S_{r+1}$

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

ull base=131;int rabin_karp(char *t,char *s){       int n=strlen(s),m=strlen(t);    if(n

动态维护子串hash

区间的$hash$是可合并的，即如果知道了$H(s,l,mid)$和$H(s,mid+1,r)$，则：

$H(s,l,r)=(H(s,l,mid)\ast B^{r-mid}+H(s,mid+1,r))modP$

问题引入

维护子串的$hash$值，有两种操作：

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

ull base=131;char s[maxn];ull sgt[maxn*4],bn[maxn]; //bn[i]=base^ivoid 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
   
    >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];}