1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 #define ull unsigned long long 5 const int maxn=1e6+5; 6 const int base=163; 7 8 char s1[10005],s2[maxn]; 9 ull p[maxn],Hash[maxn]; 10 11 void init( char *c) 12 { 13 p[0]=1; 14 Hash[0]=0; 15 int k= strlen(c+1); 16 for(int i=1;i<=k;i++) 17 p[i]=p[i-1]*base; 18 for(int i=1;i<=k;i++) 19 Hash[i]=Hash[i-1]*base + (c[i]-'A'+1); 20 } 21 ull get(int l,int r) 22 { 23 return Hash[r]-Hash[l-1]*p[r-l+1]; 24 } 25 26 int main() 27 { 28 ios::sync_with_stdio(false); 29 int T; 30 cin>>T; 31 while(T--) 32 { 33 cin>>s1; 34 cin>>s2+1; 35 init(s2); 36 int len1=strlen(s1); 37 int len2=strlen(s2+1); 38 39 int cnt=0; 40 ull pp=0; 41 for(int i=0;i<len1;i++) 42 pp=pp*base + (s1[i]-'A'+1); 43 for(int i=1; i+len1-1 <=len2;i++) 44 { 45 ull hs=get(i,i+len1-1); 46 if(hs==pp) 47 cnt++; 48 } 49 cout<<cnt<<endl; 50 } 51 }