POJ 3461

非常直白的KMP

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxw= 1e5+5;
const int maxt= 1e6+5;

char w[maxw], t[maxt];
int nxt[maxw];
int ans;

void PreKmp(int m)
{
	int i= 0, j;
	j= nxt[0]= -1;

	while (i< m){
		while (j> -1 && w[i]!= w[j]){
			j= nxt[j];
		}
		++i;
		++j;
		if (w[i]== w[j]){
			nxt[i]= nxt[j];
		}
		else{
			nxt[i]= j;
		}
	}
}
void Kmp(int p, int s)
{
	int i= 0, j= 0;
	while (j< s){
		while (i> -1 && w[i]!= t[j]){
			i= nxt[i];
		}

		++i;
		++j;
		if (i>=  p){
			++ans;
			i= nxt[i];
		}
	}
}
int main()
{
	int kase;
	scanf("%d", &kase);
 
	while (EOF!= scanf(" %s", w) && EOF!= scanf(" %s", t)){
		int w_l= strlen(w), t_l= strlen(t);
		ans= 0;
		PreKmp(w_l);
		Kmp(w_l, t_l);
		cout<<ans<<endl;
	}

	return 0;
}