题目

代码求调：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
char s[N],p[N];
int ne[N],cnt=0;
void gn(char *p,int plen) {
	ne[0]=0;
	ne[1]=0;
	for(int i=1; i<plen; i++) {
		int j=ne[i];
		while(p[i]!=p[j])j=ne[j];
		if(p[i]==p[j])ne[i+1]=ne[i]+1;
		else ne[i+1]=0;
	}
}
void kmp(char *s,char *p) {
	cnt=0;
	int l=-1,j=0,slen=strlen(s),plen=strlen(p);
	gn(p,plen);
	for(int i=0; i<slen; i++) {
		while(j&&s[i]!=p[j])j=ne[j];
		if(s[i]==p[j])j++;
		if(j==plen) {
			if(i-l>=plen) {
				cnt++;
				l=i;
			}
		}
	}
}
int main() {
	while(cin>>s) {
		if(s[0]=='#')break;
		cin>>p;
		kmp(s,p);
		cout<<cnt<<"\n";
	}
	return 0;
}