https://vjudge.net/contest/70325#overview
A::给你两个串a,b.若存在a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]. 输出最小的k.
思路：kmp返回k的位置就好了
ACcode:
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> using namespace std; int a[1000010]; int b[10010],nextt[10010]; void getNext(int b[],int len) { int m=len; nextt[1]=0; for(int k=0,q=2;q<=m;q++) { while(k>0 && b[k+1]!=b[q]) k=nextt[k]; if(b[k+1]==b[q]) k++; nextt[q]=k; } } int kmp(int a[],int b[],int LenA,int LenB) { int n=LenA,m=LenB; getNext(b,m); for(int k=0,q=1;q<=n;q++) { while(k>0 && b[k+1]!=a[q]) k=nextt[k]; if(b[k+1]==a[q]) k++; if(k==m) return q-m+1; } return -1; } int main() { ios::sync_with_stdio(false);cin.tie(0); int T,n,m; cin>>T; while(T--) { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=m;i++) cin>>b[i]; cout<<kmp(a,b,n,m)<<endl; } } B：两个串a,b .输出b在a中出现的次数思路：kmp模版
ACcode:
#include <cstring> #include <cstdio> #define t_size 1000000 #define p_size 10000 char t[t_size+5]; char p[p_size+5]; int next[p_size+5]; void prefix(char p[]) { int m=strlen(p+1); next[1]=0; for(int k=0,q=2;q<=m;q++) { while(k>0 && p[k+1]!=p[q]) k=next[k]; if(p[k+1]==p[q]) k++; next[q]=k; } } int kmp(char t[],char p[]) { prefix(p); int n=strlen(t+1),m=strlen(p+1); int sum=0; for(int i=0,q=1;q<=n;q++) { while(i>0 && p[i+1]!=t[q]) i=next[i]; if(p[i+1]==t[q]) i++; if(i==m) { sum++; i=next[i]; } } return sum; } int main(void) { int T; scanf("%d",&T); while(T--) { scanf("%s",p+1); scanf("%s",t+1); int ans=kmp(t,p); printf("%d\n",ans); } return 0; } C：一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？思路：可以用拓扑，但这里我使用KMP扩展。求出extend数组，匹配到的就加1，找到一个就跳过一个模式串的长度，继续找。
ACcode:
#include <cstdio> #include <cstring> #define size 1005 char str[size]; char mode[size]; int next[size],extend[size]; void getNext(char mode[],int next[],int modeLen) { int i,a,p; a=p=0;next[0]=modeLen; for(i=1;i<modeLen;i++) { if(i>=p || i+next[i-a]>=p) { if(i>=p) p=i; while(p<modeLen && mode[p]==mode[p-i]) ++p; next[i]=p-i; a=i; } else next[i]=next[i-a]; } } void getExtend(char str[],int strLen,int extend[],char mode[],int modeLen) { getNext(mode,next,modeLen); int a=0,p=0,sum=0; for(int i=0;i<strLen;i++) { if(i>=p || i+next[i-a]>=p) { if(i>=p) p=i; while(p<strLen && p-i <modeLen && str[p]==mode[p-i]) p++; extend[i]=p-i,a=i; } else extend[i]=next[i-a]; } } int main() { while(scanf("%s",str)==1 &&str[0]!='#') { scanf("%s",mode); int strLen=strlen(str),modeLen=strlen(mode); getExtend(str,strLen,extend,mode,modeLen); int k=0,ans=0; while(k<strLen) { if(extend[k]==modeLen) { ans++; k=k+modeLen; } else { k=k+1; } } printf("%d\n",ans); } } D:给你一串字符串，只能从前面加或后面加字符，问你最少加几次，可以让字符串有循环节,且循环次数大于1.思路：kmp前缀函数的应用，若字符串有循环节，循环节长度一定是len-next[len]…
#include <cstdio> #include <cstring> #define size 100000 char p[size+5]; int next[size+5]; void prefix(char p[]) { int m=strlen(p+1); next[1]=0; for(int k=0,q=2;q<=m;q++) { if(k>0 && p[k+1]!=p[q]) k=next[k]; if(p[k+1]==p[q]) k++; next[q]=k; } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%s",p+1); prefix(p); int len=strlen(p+1); int count=len-next[len]; printf("%d\n",(len%count==0 && len/count!=1)?0:count-len%count); } return 0; } E：字符串的所有前缀是否有循环节，若有输出循环次数思路：前缀函数的应用。
ACcode：
#include <cstdio> #include <cstring> #define size 1000000 char p[size+5]; int next[size+5]; void prefix() { int m=strlen(p+1); next[1]=0; for(int k=0,q=2;q<=m;q++) { while(k>0 && p[k+1]!=p[q]) k=next[k]; if(p[k+1]==p[q]) k++; next[q]=k; } } void print(int n) { for(int i=2;i<=n;i++) { int t=i-next[i]; if( i%t==0 && i/t!=1) printf("%d %d\n",i,i/t); } } int main() { int n; int k=1; while(scanf("%d",&n)==1&&n) { scanf("%s",p+1); printf("Test case #%d\n",k++); prefix(); print(n); printf("\n"); } } F:一个人用字符串A重复的写变成B:AAA…A，现在他把B随机分成2半.给你其中的一半，问最短可能的字符串a的长度思路:同循环节问题
ACcode：
#include <cstdio> #include <cstring> #define size 1000000 char p[size+5]; int next[size+5]; void prefix(char p[]) { int m=strlen(p+1); next[1]=0; for(int k=0,q=2;q<=m;q++) { while(k>0 && p[k+1]!=p[q]) k=next[k]; if(p[k+1]==p[q]) k++; next[q]=k; } } int main() { while(scanf("%s",p+1)!=EOF) { prefix(p); int len=strlen(p+1); printf("%d\n",len-next[len]); } return 0; } G：字符串若存在循环节，输出循环次数 #include <cstdio> #include <cstring> #include <string> using namespace std; #define T_SIZE 1000000+5 char t[T_SIZE]; int next[T_SIZE]; void prefix(char p[]) { int m=strlen(p+1); next[1]=0; for(int k=0,q=2;q<=m;q++) { while(k>0 &&p[k+1]!=p[q]) k=next[k]; if(p[k+1]==p[q]) k++; next[q]=k; } } int main() { int len1; int len2; while(gets(t+1)) { if(strcmp(t+1,".")==0)return 0; memset(next,0,sizeof(next)); prefix(t); len1=strlen(t+1); len2=len1-next[len1]; if(len1%len2==0) printf("%d\n",len1/len2); else printf("1\n"); } return 0; }H:给一字符串，找出所有既是前缀也是后缀的子串的位置
思路：ans=next[ans].递归找下去就是了。
#include <cstdio> #include <cstring> #define T_SIZE 400000+5 char p[T_SIZE]; int next[T_SIZE],res[T_SIZE]; void prefix(char p[]) { int m=strlen(p+1); next[1]=0; for(int k=0,q=2;q<=m;q++) { while(k>0&&p[k+1]!=p[q]) k=next[k]; if(p[k+1]==p[q]) k++; next[q]=k; } } int main() { int i,j; while(gets(p+1)!=NULL) { j=0; prefix(p); int len=strlen(p+1); int ans=next[len]; res[j++]=len; while(ans>0) { res[j++]=ans; ans=next[ans]; } for(i=j-1;i>0;i--) { printf("%d ",res[i]); } printf("%d\n",res[0]); } return 0; }