典型例题：给出两个字符串s1,s2,求s1在s2中出现多少次
ps.求子串的hash公式
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1e6+10;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//字符串hash模板题
char s1[maxn],s2[maxn];
ull h[maxn];
ull power[maxn]; //每一步要乘的
ull b=27,mod=1<<31;
//只有大写字母
int main(){
power[0]=1;
for(int i=1;i<=1000000;i++) power[i]=power[i-1]*b;
int t;
scanf("%d",&t);
while(t--){
scanf("%s",s1+1);
scanf("%s",s2+1);
int n=strlen(s1+1);
int m=strlen(s2+1);
h[0]=0;
ull ans=0,s=0;
for(int i=1;i<=m;i++){ //算出s2的hash值 每一位
h[i]=(h[i-1]*b+(ull)(s2[i]-‘A‘+1))%mod;
}
for(int i=1;i<=n;i++) s=(s*b+(ull)(s1[i]-‘A‘+1))%mod; //s1的hash值
for(int i=0;i<=m-n;i++){
if(s==h[i+n]-h[i]*power[n]) ans++;
}
printf("%d\n",ans);
}
return 0;
}
这道题可以直接用map来做，map<ull,int> a;
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=30010;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
int n;
int mod1=100005;
int k1=233317;
map<ull,int> a; //用map来做
char op[10],ss[210];
int main(){
scanf("%d",&n);
//int num=0;
while(n--){
scanf("%s ",op);
gets(ss);
ull num=0;
for(int i=0;i<strlen(ss);i++)
num=(num*k1+(int)ss[i]);
if(op[0]==‘f‘){
if(a[num]==1) printf("yes\n");
else printf("no\n");
}
else a[num]=1;
}
return 0;
}
给定若干个长度 ≤106 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：ababab 则最多有 3 个 ab 连接而成。
abcd 1 aaaa 4 ababab 3 .
询问每个字符串最多是由多少个相同的子字符串重复连接而成的 求最短重复子序列
这道题试问我们一个串有几个循环节。循环节就是指相等的（真）前缀和（真）后缀的个数。我们知道，
kmp过程中的next[i]是这个意义：0-i-1位中相等的真前后缀个数。那么next[len]就是指0-len-1位中相等的真前后缀个数。
所以第一种做法就是，求next数组
if(len%(len-next[len])==0) printf("%d\n",len/(len-next[len]));
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1e6+10;
const int INF=0x3fffffff;
typedef long long LL;
//询问每个字符串最多是由多少个相同的子字符串重复连接而成的 求最短重复子序列
//这道题试问我们一个串有几个循环节。循环节就是指相等的（真）前缀和（真）后缀的个数。我们知道，
//kmp过程中的next[i]是这个意义：0-i-1位中相等的真前后缀个数。那么next[len]就是指0-len-1位中相等的真前后缀个数。
char s[maxn];
int next[maxn],len;
void getnext(){
int j=-1;
int i=0;
next[0]=-1;
while(i<len){
if(j==-1||s[i]==s[j]){
i++;j++;
next[i]=j;
}
else j=next[j];
}
}
int main(){
while(1){
scanf("%s",s);
if(s[0]==‘.‘) break;
memset(next,0,sizeof(next));
len=strlen(s);
getnext();
if(len%(len-next[len])==0) printf("%d\n",len/(len-next[len]));
else printf("1\n");
}
return 0;
}
第二种做法：普通做法，hash，判断连续k个字母的hash值是不是都是一样的
//普通做法
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn = 1e6+10;
typedef unsigned long long ull;
char s1[maxn];
ull power[maxn],h[maxn];
ull n,s,base=131,mod=1<<31;
int check(ull v,int k){
for( ull i=0; i<n; i+=k ){
if(h[i+k]-h[i]*power[k]!=v) return 0; //计算字串的hash值
}
return 1;
}
int main(){
power[0]=1;
for( int i=1; i<=101000; i++ ) power[i]=power[i-1]*base;
while(scanf("%s",s1+1)){
if(s1[1]==‘.‘) break;
n=strlen(s1+1);
h[0]=0;
for( int i=1; i<=n; i++ ) h[i]=h[i-1]*base+(ull)(s1[i]-‘A‘+1);
for( int i=1; i<=n; i++ ){
if(n%i==0){
if(check(h[i],i)==1){
printf("%d\n",n/i);break;
}
}
}
}
}
给定若干字符串（这些字符串总长 ≤4×105?? ），在每个字符串中求出所有既是前缀又是后缀的子串长度。
例如：ababcababababcabab，既是前缀又是后缀的：ab，abab，ababcabab，ababcababababcabab。
前后缀：肯定就想到了next数组
这道题不需要重复求出next数组，只需要不断向前移动next
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=4e5+10;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//又是next数组？ 但是next数组是求不相交的
char s[maxn];
int next[maxn];
int len=0;
void getnext(){
int i=0,j=-1;
next[0]=-1;
while(i<len){
if(j==-1||s[i]==s[j]) {
i++;j++;
next[i]=j;
}
else j=next[j];
}
}
int op[maxn];
int main(){
while(~scanf("%s",s)){
memset(next,0,sizeof(next));
len=strlen(s);
getnext();
int num=0;
memset(op,0,sizeof(op));
//不用循环做next数组，直接取呀!!!
for(int i=len;next[i]!=-1;){
op[++num]=i; //len也写进来了
i=next[i];
}
for(int i=num;i>=1;i--) printf("%d ",op[i]);
printf("\n");
}
return 0;
}
原文：https://www.cnblogs.com/shirlybaby/p/12718694.html