Description 一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？ Input 输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。 Output 输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。 Sample Input abcde a3 aaaaaa aa # Sample Output 0 3
#include<iostream> #include<stdlib.h> #include<stdio.h> #include<algorithm> #include<cstring> using namespace std; #define MAX 1000 char T[MAX+11]; char P[MAX+11]; int next[MAX+11]; int ans; void makeNext(char P[],int next[]) { next[0] = 0; int l = strlen(P); int k = 0; for (int i = 1 ; i < l ; i++) { while (k > 0 && P[k] != P[i]) k = next[k-1]; if (P[i] == P[k]) k++; next[i] = k; } } void KMP(char T[],char P[],int next[]) { int goal = strlen(P); int length = strlen(T); makeNext(P,next); int k = 0; for (int i = 0 ; i < length ; i++) { while (k > 0 && P[k] != T[i]) k = next[k-1]; if (P[k] == T[i]) k++; if (k == goal) //匹配完成 { ans++; k = 0; //重新匹配 } } } int main() { int next[MAX+11]; while (scanf ("%s",T)!=EOF) { if (T[0] == '#') break; scanf ("%s",P); ans = 0; KMP(T,P,next); printf ("%d\n",ans); } return 0; }