POJ 3461 Oulipo KMPアルゴリズム

このアルゴリズムは去年のこの时すでに闻いたことがあって、毛片のアルゴリズムを见ますハハ..しかし、それを理解するのに長い時間がかかりました.だから私はずっと文字列の学习を排斥して、いつも难しすぎると感じて、しかしいくつかの硬い骨はやはりかじるので、この冬休み文字列をかじるのはまだいくつかの别のものがあるでしょう、KMPの学习は私は多くのブログを见てやっとそんなにいくつかの手がかりがあって、复雑度の分析は更に话すことができなくて、しかしリニアマッチングのこのようなアルゴリズムは本当に弊害があります.~问题は水问题ですが、私の最初のKMPでしょう.~

#include<iostream>

#include<cstring>

#include<string>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

#define mxt 1000005

#define mxp 10005

#define inf 0x3f3f3f3f



int f[mxp+50];

char T[mxt+50];

char P[mxp+50];



void getFail(const char *P,int *f)

{

	int m=strlen(P);

	f[0]=f[1]=0;

	for(int i=1;i<m;++i){

		int j=f[i];

		while(j&&P[i]!=P[j]) j=f[j];

		f[i+1]= P[i]==P[j]? j+1:0;

	}

}



int KMP(const char *P,const char *T,int *f)

{

	int cnt=0;int m=strlen(P),n=strlen(T);

	getFail(P,f);int j=0;

	for(int i=0;i<n;++i){

		while(j&&P[j]!=T[i]) j=f[j];

		if(P[j]==T[i]) ++j;

		if(j==m) cnt++;

	}

	return cnt;

}



int main()

{

	int ca;cin>>ca;

	while(ca--)

	{

		scanf("%s%s",P,T);

		printf("%d
",KMP(P,T,f));

	}

	return 0;

}