剪花布条
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4655 Accepted Submission(s): 3130
Problem Description
一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？
Input
输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。
Output
输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。
Sample Input
abcde a3 aaaaaa aa #
Sample Output
0 3
1 /* 功能Function Description: HDOJ-2087 2 开发环境Environment: DEV C++ 4.9.9.1 3 技术特点Technique: 4 版本Version: 5 作者Author: 可笑痴狂 6 日期Date: 20120813 7 备注Notes: 8 查找模式字串在主串中出现的次数(重复出现的模式串不能重叠)-------KMP算法 9 */ 10 11 #include<stdio.h> 12 #include<string.h> 13 14 char s[1005],t[1005]; 15 int next[1005]; 16 int k; 17 18 void get_next(int len) 19 { 20 int i,j; 21 i=0; 22 j=-1; 23 next[0]=-1; 24 while(i<len) 25 { 26 if(j==-1||t[i]==t[j]) 27 { 28 if(t[++i]==t[++j]) 29 next[i]=next[j]; 30 else 31 next[i]=j; 32 } 33 else 34 j=next[j]; 35 } 36 } 37 38 void count(int i,int len1,int len2) 39 { 40 int j=0; 41 if(i>=len1) 42 return ; 43 while(i<len1&&j<len2) 44 { 45 if(j==-1||s[i]==t[j]) //继续比较后续字符 46 { 47 ++i; 48 ++j; 49 } 50 else //模式串向右移动 51 j=next[j]; 52 } 53 if(j==len2) //匹配成功 54 ++k; 55 count(i,len1,len2); //继续在后边查找 56 } 57 58 int main() 59 { 60 int len1,len2; 61 while(scanf("%s",s)&&s[0]!='#') 62 { 63 k=0; 64 scanf("%s",t); 65 len1=strlen(s); 66 len2=strlen(t); 67 get_next(len2); 68 count(0,len1,len2); 69 printf("%d\n",k); 70 } 71 return 0; 72 }