kmp模板题
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int max_n = 1e6+100;
int net[11000];
void getnext(int p[],int psize){
net[0]=-1;p[psize]=500;
for (int i=0,j=-1;i<psize;){
if (j==-1||p[i]==p[j]){
++i;++j;
if (p[i]!=p[j])
net[i]=j;
else net[i]=net[j];
}
else j = net[j];
}
}
int kmp(int s[],int ssize,int p[],int psize){
int res = 0;
for (int i=0,j=0;i<ssize;){
if (j==-1||s[i]==p[j])++i,++j;
else j = net[j];
if (j==psize){
++res;
j = net[j];
}
}return res;
}
int p[11000];
int s[max_n];
char ss[max_n];
int main(){
int T;scanf("%d",&T);
while (T--){
scanf("%s",ss);
int m = strlen(ss);
for (int i=0;i<m;++i)p[i]=(int)ss[i];
scanf("%s",ss);
int n = strlen(ss);
for (int i=0;i<n;++i)s[i]=(int)ss[i];
getnext(p,m);
printf("%d\n",kmp(s,n,p,m));
}
}