剪花布条

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16196    Accepted Submission(s): 10265 Problem Description 一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？   Input 输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。   Output 输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。   Sample Input abcde a3 aaaaaa aa #   Sample Output 0 3   Author qianneng   Source 冬练三九之二   Recommend lcy   |   We have carefully selected several similar problems for you:   1711  1686  3746  3336  1358  解题思路：以前水过一次，普通方法能过，新学了KMP，拿简单的练练手，熟悉熟悉过程。 代码如下： #include <cstdio> #include <cstring> char s1[1010]; char s2[1010]; int next[1010]; int ans; int size1; int size2; void makenext()//打表next { memset(next,0,sizeof(next)); int k=0; size2=strlen(s2); for(int i=1;i<size2;i++) { while(k>0&&s2[k]!=s2[i]) { k=next[k-1]; } if(s2[k]==s2[i]) { k++; } next[i]=k; } } void kmp() { size1=strlen(s1); int k=0;//匹配出的长度 for(int i=0;i<size1;i++) { while(k>0&&s2[k]!=s1[i])//s2对应的k { k=next[k-1]; } if(s2[k]==s1[i]) { k++; } if(k==size2)//匹配成一次 { ans++; k=0;//清空长度 } } } int main() { while(scanf("%s",s1)!=EOF) { if(s1[0]=='#') break; scanf("%s",s2); makenext();//打表next ans=0; kmp();//匹配s1 、s2 printf("%d\n",ans); } return 0; }