HDU 2087 剪花布条(裸KMP)

#include <bits/stdc++.h>
#define maxn 1005
#define ll long long
using namespace std;
string s, p;
int Next[maxn];
int ans;

void init(){
	int j = 0, k = -1;
	int len = p.length();
	memset(Next, -1, sizeof(Next));
	while(j < len){
		if(k == -1 || p[j] == p[k]){
			k ++;
			j ++;
			Next[j] = k;
		}
		else k = Next[k];
	}
}

void kmp(){
	int i = 0, j = 0;
	int l1 = s.length();
	int l2 = p.length();
	while(i < l1){
		if(j == -1 || s[i] == p[j]){
			i ++;
			j ++;
		}
		else{
			j = Next[j];
		}
		if(j == l2){
			j = 0;
			ans ++;
		}
	}
}

int main()
{
	while(cin>>s){
		if(s == "#") break;
		cin>>p;
		init();
		ans = 0;
		kmp();
		printf("%d\n", ans);
	}
	return 0;
}