1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include <iostream> 5 #include <string> 6 using namespace std; 7 int f[ 15000]; 8 void getfill(string s) 9 {10     memset(f,0,sizeof(f));  //根据其前一个字母得到11     for(int i=1;i<s.size();i++)12     {13         int j=f[i];14         while(j && s[i]!=s[j])15             j=f[j];16         f[i+1]=(s[i]==s[j])?j+1:0;17     }18 }19 int find(string a,string s)20 {21     int ans=0;22     getfill(s);int j=0;23     for(int i=0;i<a.size();i++)24     {25         while(j && a[i]!=s[j])26             j=f[j];27         if(a[i]==s[j])28             j++;29         if(j==s.size()){30             ans++;31         }32     }33     return ans;34 }35 int main()36 {37     string s,a;38     int T;39     scanf("%d",&T);40     while(T--)41     {42         getchar();43         cin>>s>>a;44         int ans=find(a,s);45         printf("%d\n",ans);46     }47     return 0;48 }