剪花布条
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11304 Accepted Submission(s): 7259Problem Description一块花布条,里面有些图案,另有一块直接可用的小饰条,里面也有一些图案。对于给定的花布条和小饰条,计算一下能从花布条中尽可能剪出几块小饰条来呢?Input输入中含有一些数据,分别是成对出现的花布条和小饰条,其布条都是用可见ASCII字符表示的,可见的ASCII字符有多少个,布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符,则不再进行工作。Output输出能从花纹布中剪出的最多小饰条个数,如果一块都没有,那就老老实实输出0,每个结果之间应换行。Sample Inputabcde a3aaaaaa aa#Sample Output03AuthorqiannengSource
汉语题~
1 #include<iostream> 2 #include<vector> 3 #include <cstdio> 4 #include <cstring> 5 #include <cstdlib> 6 #include <math.h> 7 #include<algorithm> 8 #define ll long long 9 #define eps 1e-8 10 using namespace std; 11 12 int nexts[1050]; 13 char str[1050],b[1050]; 14 15 void pre_nexts(int m) 16 { 17 memset(nexts,0,sizeof(nexts)); 18 int j = 0,k = -1; 19 nexts[0] = -1; 20 while(j < m) 21 { 22 if(k == -1 || b[j] == b[k]) nexts[++j] = ++k; 23 else k = nexts[k]; 24 } 25 } 26 int KMP(int n,int m) 27 { 28 int i,j = 0,cnt = 0; 29 for(i = 0; i < n; i++) 30 { 31 while(j > 0 && str[i] != b[j]) 32 j = nexts[j]; 33 if(str[i] == b[j]) 34 { 35 j++; 36 } 37 if(j == m)cnt++,j++; //(出现个数) 38 //j = nexts[j];(出现次数) 注意区分 39 } 40 return cnt; 41 } 42 int main(void) 43 { 44 while(scanf("%s",str),str[0] != '#') 45 { 46 scanf("%s",b); 47 if((int)strlen(b) > (int)strlen(str)) 48 { 49 printf("0 "); continue; 50 } 51 else 52 { 53 pre_nexts((int)strlen(b)); 54 printf("%d ",KMP((int)strlen(str),(int)strlen(b))); 55 } 56 } 57 return 0; 58 }