目的：找出字符串S的所有后缀与字符串T的最长公共前缀，预处理Next[i]。
S字符串长度为n，T字符串长度为m。
Next[i]，i∈[0,m)，表示T的后缀i与T的最长公共前缀。
extend[i]，i∈[0,n)，表示T与S[i,n)的最长公共前缀。如果有一个extend[i]=m,则T在S中在i位置出现。
时间复杂度：O(|S|+|T|)
自用模板：
#include <iostream> #include <string.h> using namespace std; const int maxn=1100; int Next[maxn],extend[maxn]; void get_Next(char *s) { int n=strlen(s); int i,j,k; for(j=0;1+j<n&&s[j]==s[1+j];j++); Next[1]=j; k=1; for(i=2;i<n;i++) { int len=k+Next[k],L=Next[i-k]; if(L<len-i) { Next[i]=L; } else { for(j=max(0,len-i);i+j<n&&s[j]==s[i+j];j++); Next[i]=j; k=i; } } Next[0]=n; } void ex_kmp(char *T,char *s) { int n=strlen(T),m=strlen(s); int i,j,k; for(j=0;j<n&&j<m&&T[j]==s[j];j++); extend[0]=j; k=0; for(i=1;i<n;i++) { int len=k+extend[k],L=Next[i-k]; if(L<len-i) { extend[i]=L; } else { for(j=max(0,len-i);j<m&&i+j<n&&s[j]==T[i+j];j++); extend[i]=j; k=i; } } } //定义母串为s,字串为T，s的长度为n，T的长度为m,求T与S的每一个后缀的最长公共前缀 //设extend数组，extend[i]表示T与S[i,n-1]的最长公共前缀，i从0到n-1，如果有一个extend[i]=m,则T在S中在i位置出现。 int main() { char s[maxn],T[maxn]; cin>>T>>s; //找出T的所有后缀与s的最长公共前缀 get_Next(s); ex_kmp(T,s); for(int i=0;i<strlen(T);i++) { cout<<extend[i]<<" "; } cout<<endl; return 0; }
修改模板：
①配合fail数组进行去重
int len2=len-fail[len-1]-1;如果len%len2!=0则不必去重，再把len赋值给len2即可。如123123123需要去重，12312312则不需要。
fail数组：设j=fail[i]，满足s0...j=sj-i...i到si的最大的j
| len=8 | a | a | b | a | b | a | a | b |
| fail[] | -1 | 0 | -1 | 0 | -1 | 0 | 1 | 2 |
#include<bits/stdc++.h> using namespace std; const int maxn=100050; void getfail(char *p,int *fail) { int match=-1; fail[0]=-1; for(int i=1;p[i];i++) { while(match>=0&&p[match+1]!=p[i]) { match=fail[match]; } if(p[match+1]==p[i]) match++; fail[i]=match; } } int main() { char s[maxn]; int fail[maxn]; cin>>s; //对s进行去重，len2是去重后长度 getfail(s,fail); int len=strlen(s),len2; len2=len-fail[len-1]-1; if(len%len2!=0)len2=len; cout<<len2<<endl; return 0; }
②修改get_Next函数
Next[i]表示Ti...len-1与T的最长公共前缀，做了一个return max的修改
| len=9 | a | a | a | b | a | a | a | a | b |
| Next[] | 9 | 2 | 1 | 0 | 3 | 4 | 2 | 1 | 0 |
int get_Next(char *s) { int n=strlen(s),ans=0; int i,j,k; for(j=0;1+j<n&&s[j]==s[1+j];j++); Next[1]=j; k=1; for(i=2;i<n;i++) { int len=k+Next[k],L=Next[i-k]; if(L<len-i) { Next[i]=L; } else { for(j=max(0,len-i);i+j<n&&s[j]==s[i+j];j++); Next[i]=j; k=i; } if(Next[i]>ans) ans=Next[i]; } Next[0]=n; return ans; }
hdu4300，给加密方式，再给密文+部分或者全部明文，输出密文+明文，将给的串全部解密or加密，然后求两串前后缀相同部分，即可找出密文长度
我总觉得这题是在演我
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+100; int Next[maxn],extend[maxn]; void get_Next(char *s) { int n=strlen(s); int i,j,k; for(j=0;1+j<n&&s[j]==s[1+j];j++); Next[1]=j; k=1; for(i=2;i<n;i++) { int len=k+Next[k],L=Next[i-k]; if(L<len-i) { Next[i]=L; } else { for(j=max(0,len-i);i+j<n&&s[j]==s[i+j];j++); Next[i]=j; k=i; } } Next[0]=n; } int ex_kmp(char *T,char *s) { int n=strlen(T),m=strlen(s),res=m; //res=0然后wa了很多发，明文可能没有 int i,j,k; for(j=0;j<n&&j<m&&T[j]==s[j];j++); extend[0]=j; k=0; for(i=1;i<n;i++) { int len=k+extend[k],L=Next[i-k]; if(L<len-i) { extend[i]=L; } else { for(j=max(0,len-i);j<m&&i+j<n&&s[j]==T[i+j];j++); extend[i]=j; k=i; } if(extend[i]+i>=n&&i>=extend[i])return i; } return res; } int main() { int T; scanf("%d",&T); while(T--) { char s[maxn],t[maxn],ch[30]; int mp[30],lens; scanf("%s",ch); for(int i=0;i<26;i++)mp[ch[i]-'a']=i; scanf("%s",s); lens=strlen(s); for(int i=0;i<lens;i++) { t[i]=mp[s[i]-'a']+'a'; } t[lens]=' '; get_Next(t); int place=ex_kmp(s,t);//s的所有后缀与t的最长公共前缀 for(int i=0;i<place;i++)printf("%c",s[i]); for(int i=0;i<place;i++)printf("%c",mp[s[i]-'a']+'a'); printf(" "); } return 0; }
fzu1901，找满足S[i]=S[i+P]的所有i，卡常
#include<stdio.h> #include<iostream> #include<string.h> #include<stack> using namespace std; const int maxn=1e6+10; int Next[maxn],extend[maxn]; void get_next(char *s) { int n=strlen(s),i,j,k; for(j=0;1+j<n&&s[j]==s[1+j];j++); Next[1]=j; k=1; for(i=2;i<n;i++) { int len=k+Next[k],L=Next[i-k]; if(L<len-i)Next[i]=L; else { for(j=max(0,len-i);i+j<n&&s[j]==s[i+j];j++); Next[i]=j; k=i; } } } int a[maxn]; int main() { int T,t=1; scanf("%d",&T); while(T--) { char ch[maxn]; scanf("%s",ch); get_next(ch); int tmp=0,len=strlen(ch); for(int i=0;i<len;i++) { if(Next[i]+i==len) a[tmp++]=i; } printf("Case #%d: %d ",t++,tmp+1); for(int i=0;i<tmp;i++) { printf("%d ",a[i]); } printf("%d ",len); } return 0; }
...