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[100005],t[1000005]; int tot,nxt[1000005]; void kmp_pre(){ int i,j; int len=strlen(s); j=nxt[0]=-1;i=0; while(i<len){ while(j!=-1 && 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=0; while(i<n){ while(j!=-1 && t[i]!=s[j]) j=nxt[j]; ++i,++j; if(j==m){ ans++; j=nxt[j]; } } printf("%d ",ans); } int main(){ int tt; scanf("%d",&tt); while(tt--){ memset(nxt,0,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,0,sizeof nxt); int i,j; i=0;j=nxt[0]=-1; while(i<m){ while(j!=-1 && b[i]!=b[j])j=nxt[j]; nxt[++i]=++j; } } void kmp(){ int i,j,ans; i=j=ans=0; while(i<n){ while(j!=-1 && a[i]!=b[j])j=nxt[j]; ++i;++j; if(j==m){ printf("%d ",i-j+1); return; } } puts("-1"); return; } int main(){ int t; cin >> t; while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++)scanf("%d",&a[i]); for(int i=0;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,0,sizeof nxt); int i,j; i=0;j=nxt[0]=-1; while(i<m){ while(j!=-1 && s[i]!=s[j])j=nxt[j]; nxt[++i]=++j; } } int main(){ int tt=0; while(scanf("%d",&m),m){ printf("Test case #%d ",++tt); scanf("%s",s); kmp_pre(); for(int i=2;i<=m;i++){ if(i%(i-nxt[i])==0 && i/(i-nxt[i])>1) printf("%d %d ",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,0,sizeof nxt); m=strlen(s); int i,j; i=0;j=nxt[0]=-1; while(i<m){ while(j!=-1 && s[i]!=s[j])j=nxt[j]; nxt[++i]=++j; } } int main(){ while(scanf("%s",s)&&strcmp(s,".")){ kmp_pre(); int ans=1; if(m%(m-nxt[m])==0)ans=m/(m-nxt[m]); printf("%d ",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,0,sizeof nxt); int i,j; i=0;j=nxt[0]=-1; while(i<m){ while(j!=-1 && 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=0,cnt[maxn]={}; cnt[0]=0,cnt[1]=1; for(int i=2;i<=m;i++) cnt[i]=(cnt[nxt[i]]+1)%mod; for(int i=1;i<=m;i++)ans=(ans+cnt[i])%mod; printf("%d ",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,0,sizeof nxt); m=strlen(s); int i,j; i=0;j=nxt[0]=-1; while(i<m){ while(j!=-1 && 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]==0)printf("%d ",m); else if(m%(m-nxt[m])==0)puts("0"); else { int cir=m-nxt[m]; printf("%d ",cir-nxt[m]%cir); } } }
*hdu2594 后缀套后缀
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define maxn 50005 char s1[maxn<<1],s2[maxn<<1]; int n,m,nxt[maxn<<1]; void kmp_pre(){ memset(nxt,0,sizeof nxt); int len=strlen(s1); int i=0,j=-1; nxt[0]=-1; while(i<len){ while(s1[i]!=s1[j] && j!=-1) 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==0){ printf("0 "); continue; } else { while(ans>minlen) ans=nxt[ans]; char tmp[maxn]={}; strncpy(tmp,s1,ans); printf("%s %d ",tmp,ans); } } return 0; }