题意:
给你一个T串和P串,问你P串在T串中出现了多少次.
分析:
直接套用KMP模板即可. 注意失配指针最后一个'\0'也有定义.
#include<cstdio>
#include<iostream>
#include<cstring>using namespace std;
const int maxn = 1e7;
char T[1000000+111],P[11111];
int f[11111];
int cnt;void find(char *T,char *P,int *f)
{int n=strlen(T);int m=strlen(P);int j=0;for(int i=0;i<n;i++){if(j && T[i]!=P[j])j=f[j];if(T[i]==P[j])j++;if(j==m)cnt++;//次数++}
}void getfail(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 main()
{int k;cin>>k;while(k--){cnt=0;scanf("%s%s",P,T);getfail(P,f);find(T,P,f);printf("%d\n",cnt);}}