next数组的含义：next[i]表示以字符串s的第i个字符为结尾的后缀与s前缀匹配的长度
next数组也可以当做fail数组，即当模式串s[j]与串t[i]不匹配时，只要将j转换到next[j]继续匹配即可
在求s的next数组时，也用同样的原理，当s[j]与s[i]不匹配时，只要将j转换到next[j]继续匹配即可，当 注意此时模式串的首字母是s[0]
poj3461
//next[i]表示和模式串第i位匹配失败时，再去和模式串第next[i]位匹配
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char s[],t[];
int tot,nxt[];
void kmp_pre(){
int i,j;
int len=strlen(s);
j=nxt[]=-;i=;
while(i<len){
while(j!=- && s[i]!=s[j]) j=nxt[j];
nxt[++i]=++j;
}
}
void kmp(){
int i,j,ans;
int m=strlen(s);
int n=strlen(t);
i=j=ans=;
while(i<n){
while(j!=- && t[i]!=s[j]) j=nxt[j];
++i,++j;
if(j==m){
ans++;
j=nxt[j];
}
}
printf("%d\n",ans);
}
int main(){
int tt;
scanf("%d",&tt);
while(tt--){
memset(nxt,,sizeof nxt);
scanf("%s%s",s,t);
kmp_pre();
kmp();
}
}
hdu1711 求最左边匹配位
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 1000005
int nxt[maxn],a[maxn],b[maxn],n,m;
void kmp_pre(){
memset(nxt,,sizeof nxt);
int i,j;
i=;j=nxt[]=-;
while(i<m){
while(j!=- && b[i]!=b[j])j=nxt[j];
nxt[++i]=++j;
}
}
void kmp(){
int i,j,ans;
i=j=ans=;
while(i<n){
while(j!=- && a[i]!=b[j])j=nxt[j];
++i;++j;
if(j==m){
printf("%d\n",i-j+);
return;
}
}
puts("-1");
return;
}
int main(){
int t;
cin >> t;
while(t--){
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)scanf("%d",&a[i]);
for(int i=;i<m;i++)scanf("%d",&b[i]);
kmp_pre();
kmp();
}
}
poj1961 求循环节
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 1000005 int m,nxt[maxn];
char s[maxn];
void kmp_pre(){
memset(nxt,,sizeof nxt);
int i,j;
i=;j=nxt[]=-;
while(i<m){
while(j!=- && s[i]!=s[j])j=nxt[j];
nxt[++i]=++j;
}
} int main(){
int tt=;
while(scanf("%d",&m),m){
printf("Test case #%d\n",++tt);
scanf("%s",s);
kmp_pre();
for(int i=;i<=m;i++){
if(i%(i-nxt[i])== && i/(i-nxt[i])>)
printf("%d %d\n",i,i/(i-nxt[i]));
}
puts("");
}
}
poj2406 求最小循环节
//如果将s数组右移一维，那么nxt[i]就是：后缀s[i]与s前缀匹配的长度
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 1000005 int m,nxt[maxn];
char s[maxn]; void kmp_pre(){
memset(nxt,,sizeof nxt);
m=strlen(s);
int i,j;
i=;j=nxt[]=-;
while(i<m){
while(j!=- && s[i]!=s[j])j=nxt[j];
nxt[++i]=++j;
}
} int main(){
while(scanf("%s",s)&&strcmp(s,".")){
kmp_pre();
int ans=;
if(m%(m-nxt[m])==)ans=m/(m-nxt[m]);
printf("%d\n",ans);
} }
hdu3336 next数组+线性dp
//cnt[i]表示以s[i]结尾的串可以匹配的前缀数
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define mod 10007
#define maxn 200005 int m,t,nxt[maxn];
char s[maxn];
void kmp_pre(){
memset(nxt,,sizeof nxt);
int i,j;
i=;j=nxt[]=-;
while(i<m){
while(j!=- && s[i]!=s[j])j=nxt[j];
nxt[++i]=++j;
}
} int main(){
scanf("%d",&t);
while(t--){
scanf("%d%s",&m,s);
kmp_pre();
int ans=,cnt[maxn]={};
cnt[]=,cnt[]=;
for(int i=;i<=m;i++)
cnt[i]=(cnt[nxt[i]]+)%mod;
for(int i=;i<=m;i++)ans=(ans+cnt[i])%mod;
printf("%d\n",ans);
}
}
*hdu3746 循环节应用
/*
最小循环节=串长-末位匹配长度
*/#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 100005 int nxt[maxn],m;
char s[maxn];
void pre_kmp(){
memset(nxt,,sizeof nxt);
m=strlen(s);
int i,j;
i=;j=nxt[]=-;
while(i<m){
while(j!=- && s[i]!=s[j])j=nxt[j];
nxt[++i]=++j;
}
} int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%s",s);
pre_kmp();
if(nxt[m]==)printf("%d\n",m);
else if(m%(m-nxt[m])==)puts("");
else {
int cir=m-nxt[m];
printf("%d\n",cir-nxt[m]%cir);
}
}
}
*hdu2594 后缀套后缀
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 50005
char s1[maxn<<],s2[maxn<<];
int n,m,nxt[maxn<<]; void kmp_pre(){
memset(nxt,,sizeof nxt);
int len=strlen(s1);
int i=,j=-;
nxt[]=-;
while(i<len){
while(s1[i]!=s1[j] && j!=-)
j=nxt[j];
nxt[++i]=++j;
}
}
int main(){
while(~scanf("%s%s",s1,s2)){
n=strlen(s1);
m=strlen(s2);
int minlen=min(n,m);
strcat(s1,s2);
kmp_pre(); int len=strlen(s1),ans=nxt[len];
if(ans==){
printf("0\n");
continue;
}
else {
while(ans>minlen)
ans=nxt[ans];
char tmp[maxn]={};
strncpy(tmp,s1,ans);
printf("%s %d\n",tmp,ans);
}
}
return ;
}