自己做的第一道字符串匹配的题目,纯模板题。哎,初学KMP,纪念一下吧
#include<iostream> #include<cstdio> #include<cstring> char P[10005],T[1000005]; int next[10005]; void init_next() { int k,m=strlen(P); next[1]=0; k=0; for(int i=1;i<m;i++) { while(k>0&&P[k]!=P[i]) k=next[k]; if(P[k]==P[i]) k++; next[i+1]=k; } } int KMP() { int n=strlen(T); int m=strlen(P); int q=0; int ans=0; for(int i=0;i<n;i++) { while(q>0&&P[q]!=T[i]) q=next[q]; if(P[q]==T[i]) q++; if(q==m) { ans++; q=next[q]; } } return ans; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%s%s",P,T); init_next(); printf("%d\n",KMP()); } return 0; }