KMP板子，好久以前学过了，直接把板子粘上去即可。

#include
     
      #include
      
       using namespace std;char s1[1000001];char s2[10001];int nxt[10001]={
   0};void getnext(int m){    int j=0;    for(int i=2;i<=m;i++){    while(j!=0&&s2[j+1]!=s2[i])j=nxt[j];    if(s2[j+1]==s2[i])j++;    nxt[i]=j;    }    return;}int ans;void KMP(int n,int m){    int j=0;    for(int i=1;i<=n;i++){    while(j!=0&&s2[j+1]!=s1[i])j=nxt[j];    if(s2[j+1]==s1[i])j++;    if(j==m){        ans++;        j=nxt[j];    }    }    return;}int main(){    int t;    scanf("%d",&t);    while(t--){    ans=0;    memset(nxt,0,sizeof(nxt));    scanf("%s%s",s2+1,s1+1);    int n=strlen(s1+1),m=strlen(s2+1);    getnext(m);    KMP(n,m);    printf("%d\n",ans);    }    return 0;}