1 #include<stdio.h> 2 #include<string.h> 3 const int maxn=10000+5,maxm=1000000+10; 4 char word[maxn],text[maxm]; 5 int next[maxn]; 6 void get_next(int n) 7 { 8     int i=0,j=-1; 9     next[i]=j;10     while(i<n){11         if(j==-1 || word[i]==word[j]) {j++;i++;next[i]=j;}12         else j=next[j];13     }14 }15 int get_occurrence(int len1,int len2)16 {17     int i=0,j=0,num=0;18     while(i<len2 && j<len1){19         if(j==-1 || word[j]==text[i]) {i++;j++;}20         else j=next[j];21         if(j==len1){22             num++;23             j=next[j];24         }25     }26     return num;27 }28 int main()29 {30     int t;31     scanf("%d",&t);32     while(t--){33         scanf("%s%s",word,text);34         int len1=strlen(word),len2=strlen(text);35         get_next(len1);36         int ans=get_occurrence(len1,len2);37         printf("%d\n",ans);38     }39     return 0;40 }