求第一个字符串在第二个字符串中出现的次数
简单KMP算法题
#include<stdio.h> #include<string.h> int n,m; char a[1000002],b[10002]; int p[10002]; void getp(){ p[1]=0; int i,j=0; for(i=2;i<=m;i++){ while(j>0&&b[j+1]!=b[i]) j=p[j]; if(b[j+1]==b[i]) j+=1; p[i]=j; } } int kmp() { int i,j=0,ans=0; for(i=1;i<=n;i++){ while(j>0&&b[j+1]!=a[i]) j=p[j]; if(b[j+1]==a[i]) j+=1; if(j==m) { ans++; j=p[j]; } } return ans; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%s%s",b+1,a+1); n=strlen(a+1); m=strlen(b+1); getp(); printf("%d\n",kmp()); } return 0; }