这个算法去年的这个时候就已经听过了,看毛片算法哈哈..不过理解它确实花了我很久的时间..以致于我一直很排斥字符串的学习,因为总觉得太难了,但是有些硬骨头还是要啃的,这个寒假就啃啃字符串还有一些别的东西吧,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\n",KMP(P,T,f));
}
return 0;
}