http://acm.hdu.edu.cn/showproblem.php?pid=2087
剪花布条
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4547 Accepted Submission(s): 3061
Problem Description
一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？
Input
输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。
Output
输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。
Sample Input
abcde a3 aaaaaa aa #
Sample Output
0 3
View Code
1 #include<stdio.h> 2 #include<string.h> 3 char T[1005],S[1005]; 4 int lenS,lenT; 5 int count() 6 { 7 int count=0; 8 int i=0; 9 int j=0; 10 11 while(i<lenT&&j<lenS) 12 { 13 if(S[j]==T[i]) 14 { 15 i++; 16 j++; 17 } 18 else 19 { 20 i=i-j+1; 21 j=0; 22 } 23 if(j>lenS-1) 24 { 25 count++; 26 j=0; 27 } 28 } 29 printf("%d\n",count); 30 31 } 32 int main() 33 { 34 while(~scanf("%s",T)) 35 { 36 if(T[0]=='#') break; 37 scanf("%s",S); 38 lenT=strlen(T); 39 lenS=strlen(S); 40 count(); 41 } 42 }
KMP方法：
View Code
1 #include<stdio.h> 2 #include<string.h> 3 char T[1005],S[1005]; 4 int lenT; 5 int lenS; 6 int next[1005]; 7 void get_next() 8 { 9 int i=1; 10 next[1]=0; 11 int j=0; 12 while(i<lenS) 13 { 14 if(j==0||S[i]==S[j]) 15 { 16 i++; 17 j++; 18 next[i]=j; 19 } 20 else j=next[j]; 21 } 22 } 23 void kmp() 24 { 25 int i=1; 26 int j=1; 27 int count=0; 28 while(i<=lenT&&j<=lenS) 29 { 30 if(j==0||T[i]==S[j]) 31 { 32 i++; 33 j++; 34 } 35 else 36 { 37 j=next[j]; 38 } 39 if(j>lenS) 40 { 41 count++; 42 j=1; 43 } 44 } 45 printf("%d\n",count); 46 } 47 48 int main() 49 { 50 while(~scanf("%s",T+1)) 51 { 52 53 if(T[1]=='#') break; 54 55 scanf("%s",S+1); 56 57 lenS=strlen(S+1); 58 59 lenT=strlen(T+1); 60 61 //printf("%d\n",lenS); 62 63 kmp(); 64 } 65 66 }