POJ3461 (C++)

poj3461.cpp

#include <stdio.h>
#include <string.h>

const int maxn=10005,maxm=1000005;

int next[maxn],n;
char text[maxm],pat[maxn];

inline void get_next() {
  int m=strlen(pat),k=-1;
	next[0]=-1;
	for (int q=1; q<m; q++) {
		while (k>-1 && pat[k+1]!=pat[q]) k=next[k];
		if (pat[k+1]==pat[q]) k++;
		next[q]=k;
	}
}

int kmp_match() {
	int ans=0,m=strlen(pat),n=strlen(text);
	int q=-1;
	for (int i=0; i<n; i++) {
		while (q>-1 && pat[q+1]!=text[i]) q=next[q];
		if (pat[q+1]==text[i]) q++;
		if (q==m-1) {
			ans++;
			q=next[q];
		}
	}
	return ans;
}

int main() {
	scanf("%d",&n);
	while (n--) {
		scanf("%s%s",pat,text);
		get_next();
		printf("%d\n",kmp_match());
	}
	return 0;
}