题意：
2个字符串A,B.问A中有多少个字符串B.
Input
输入中含有一些数据，分别是成对出现A,B A和B不会超过1000个字符。 如果遇见#字符，则表示测试结束。
Output
输出B的个数，每个结果之间应换行。
KMP模板题：
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 using namespace std; typedef unsigned long long ull; typedef long long ll; const int maxN=1e3+5; char a[maxN], b[maxN]; int nex[maxN]; void cal_next(int len) { nex[0]=-1; int k = -1; for(int i=1; i<len; i++) { while(k>-1 && nex[k+1]!=b[i]) { k = nex[k]; } if(nex[k+1] == b[i]) k++; nex[i]=k; } } int KMP(int sa, int ea, int len) { int k = -1; for(int i=sa; i<ea; i++) { while(k>-1 && a[i]!=b[k+1]) { k = nex[k]; } if(b[k+1] == a[i]) k++; if(k == len-1) return i-len+1; } return -1; } int main() { while(scanf("%s %s", a, b)!=EOF) { if(a[0]=='#') break; int lena=(int)strlen(a), lenb=(int)strlen(b); cal_next(lenb); int tmp=0, now=0, ans=0; while(lena-now>=lenb && (tmp=KMP(now, lena, lenb))!=-1 ) { ans++; now = tmp + lenb; } printf("%d\n", ans); getchar(); } return 0; }
