字符串_哈希

 参考文章：

E. Compress Words(字符串hash)_z听歌的小孩z的博客-CSDN博客

字符串哈希 - OI Wiki (oi-wiki.org)

板子：

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+50;
typedef long long ll;
const int mod=1e9+7;
typedef unsigned long long ull;
char s[N];
int n;
ll h[N],p[N],base=31;
void init(){p[0]=1;for(int i=1;i<=n;i++){h[i]=(h[i-1]*base%mod+s[i])%mod;p[i]=p[i-1]*base%mod;}
}
int get_v(int l,int r){return ((h[r]-h[l-1]*p[r-l+1]%mod)%mod+mod)%mod;
}int main(){scanf("%s",s+1);n=strlen(s+1);init();return 0;
}
/*
ll p[3][N],h[3][N];
ll mod[3]={100000007,998244353,100000009},base[3]={73,87,61};
*/

例题： 

例1：2021_ICPC_山东 F- Birthday Cake - Codeforces（双哈希）

题解： 

看一个字符串的前缀和后缀,如果这两个前后缀相等，就去查询这个字符串除去这个前后缀之后还剩下的部分是否出现过，然后统计出现次数的答案 ps 我们把所有串按照串的长度从小到大排个序，一定要排，不然aaaa,aa这个数据就可以卡掉。 

/*eg：abcabcd    l=7 j=3 r=l-j+1=5 前缀[1,3] 后缀[5,7]chk(1,3)==chk(5,7)chk(4,6)
*/

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
typedef long long ll;
typedef pair<ll,ll> pi;
const ll mod1=1e9+7,mod2=1e9+9;string s[N];
char ss[N];
int n;
ll res;
bool cmp(string x,string y){return x.length()<y.length();
}
ll p1[N],p2[N],h1[N],h2[N],P=31;
void init(){p1[0]=p2[0]=1;for(int i=1;i<N;i++)p1[i]=p1[i-1]*P%mod1,p2[i]=p2[i-1]*P%mod2;
}void get_h(int n){for(int i=1;i<=n;i++){h1[i]=(h1[i-1]*P%mod1+ss[i])%mod1;h2[i]=(h2[i-1]*P%mod2+ss[i])%mod2;}
}
ll getv1(int l,int r){return (h1[r]-h1[l-1]*p1[r-l+1]%mod1+mod1)%mod1;
}
ll getv2(int l,int r){return (h2[r]-h2[l-1]*p2[r-l+1]%mod2+mod2)%mod2;
}
map<pi,int>mp;
int main(){init();scanf("%d",&n);for(int i=1;i<=n;i++)cin>>s[i];sort(s+1,s+1+n,cmp);for(int i=1;i<=n;i++){int len=s[i].length();for(int j=0;j<len;j++)ss[j+1]=s[i][j];get_h(len);//前缀==后缀for(int j=1;j<len-j+1;j++){//[1,j][r,len]int r=len-j+1;if(getv1(1,j)==getv1(r,len)&&getv2(1,j)==getv2(r,len)){//除去前后缀的部分 [j+1,r-1]res+=mp[{getv1(j+1,r-1),getv2(j+1,r-1)}];}}ll v1=getv1(1,len),v2=getv2(1,len);//printf("end");//printf("i:%d [1,%d] [%d,%d] res%d\n",i,j,r,len,res);//printf("v1 %lld v2 %lld\n",v1,v2);res+=mp[{v1,v2}];mp[{v1,v2}]++;//printf("i:%d [1,%d] [%d,%d] res%d\n",i,j,r,len,res);}printf("%lld",res);return 0;
}

例2：E - Compress Words- Codeforces（双哈希）

题解：从长到短枚举每一个单词的前缀，和前面的所有单词匹配

*单哈希会被卡

*必须和前面所有单词匹配，不能只和前一个单词匹配

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pi;
const ll mod[2]={100000007,100000009};int n,cnt;
char s[N],ss[N];ll h1[3][N],h2[3][N],p[3][N],P[3]={73,87,61};
int l1,l2;
inline void init(){p[0][0]=p[1][0]=p[2][0]=1;for(int k=0;k<2;k++)for(int i=1;i<N;i++)p[k][i]=(p[k][i-1]*P[k])%mod[k];
}
inline void geth(int n,int num){for(int j=0;j<num;j++)for(int i=1;i<=n;i++)h1[j][i]=((h1[j][i-1]*P[j])%mod[j]+s[i])%mod[j];
}inline ll getv2(int l,int r,int i){return ((h2[i][r]-(h2[i][l-1]*p[i][r-l+1])%mod[i])%mod[i]+mod[i])%mod[i];
}
int main(){init();scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s+1);l1=strlen(s+1);//printf("i%d %s l1:%d\n",i,s+1,l1);geth(l1,2);int anj=1;//printf("l2:%d l1:%d l2-l1+1:%d\n",l2,l1,l2-l1+1);int j1=l1,j2=l2-l1+1;if(j2<1)j1+=j2-1,j2=1;for(;j1>0&&j2<=l2;j1--,j2++){//printf("[1,%d]%lld [%d,%d]%lld %lld %lld %lld %lld\n",j1,h1[0][j1],j2,l2,getv2(j2,l2,0),h1[1][j1],getv2(j2,l2,1),h1[2][j1],getv2(j2,l2,2));if(h1[0][j1]==getv2(j2,l2,0)&&h1[1][j1]==getv2(j2,l2,1)){anj=j1+1;//printf("anj %d\n",anj);break;}}int t=cnt;for(int j=anj;j<=l1;j++)ss[++cnt]=s[j];//printf("cnt%d %s\n",cnt,ss+1);for(int j=0;j<2;j++)for(int i=t;i<=cnt;i++)h2[j][i]=((h2[j][i-1]*P[j])%mod[j]+ss[i])%mod[j];l2=cnt;}printf("%s",ss+1);return 0;
}