剪花布条

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16206    Accepted Submission(s): 10272 Problem Description 一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？   Input 输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。   Output 输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。   Sample Input abcde a3 aaaaaa aa #   Sample Output 0 3   KMP的模板题，也可用直接查找的方法，毕竟字符数组很小 #include<cstdio> #include<cstring> #define N 1005 char str[N],ptr[N]; int next[N];//前缀数组 void get() { next[0]=-1;//设 next[0]为-1，还有的人设为0，这都行，只是形式有点变化 int i=0,k=-1; int s=strlen(str); while(i<s-1) { if(k==-1||str[i]==str[k]) { i++; k++; next[i]=k; } else k=next[k]; } } void kmp() { int ans=0; int p=strlen(ptr); int s=strlen(str); int i=0,j=0; while(i<p) { while(j!=-1&&str[j]!=ptr[i]) j=next[j]; i++; j++; if(j==s) { ans++; j=0; } } printf("%d\n",ans); } int main() { while(scanf("%s",ptr)&&ptr[0]!='#') { scanf("%s",str); get(); kmp(); } return 0; }