fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define sz 10000000
  3. #define ll long long
  4. using namespace std;
  5. const int mod=1e9+7;
  6. int ara[sz];
  7. string s1,s2;
  8. int main()
  9. {
  10.     int test,i,cs=1;
  11.     cin>>test;
  12.     while(test--)
  13.     {
  14.         cin>>s1>>s2;
  15.         int hs=0 ;
  16.  
  17.         for(i=0;i<s1.size();i++)
  18.         {
  19.             hs=((ll)hs*29+(ll)(s1[i]-'a')%(ll)mod)%mod;
  20.             ara[i+1]=hs;
  21.         }
  22.  
  23.         ll int pw=1;
  24.         hs=0;
  25.        for(i=0;i<s2.size();i++)
  26.         {
  27.  
  28.             hs=(ll)hs*29+(ll)(s2[i]-'a')%(ll)mod;
  29.             pw=(pw*(ll)29)%(ll)mod;
  30.         }
  31.  
  32.         int dif=s1.size()-s2.size()+1,cnt=0,s=0,res,ans,az;
  33.         for(i=1;i<=dif;i++)
  34.         {
  35.             res=i+s2.size()-1;
  36.             ans=((ll)ara[res]-(ll)ara[i-1]*pw)%(ll)mod;
  37.             ans=((ll)ans%(ll)mod+(ll)mod)%(ll)mod;
  38.             if(ans==hs)s++;
  39.         }
  40.         cout<<"Case "<<cs++<<": "<<s<<endl;
  41.     }
  42.     return 0;
  43.  
  44. }
  45.  
Success #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
5
abdxabddabdabddabddabcy
abddabcy
ababcabcabababd
ababd
ooooooooooooooooomooooomonmonnnnnnnnnnnnnnnnnnnnnnnnmmmnnnnnmmmmmmmmnnnmm
mn
aaaaaaaaaaanaaaaaaaaaaaaazzzzzzzzzqacacabacacabacacacacacabacacabacacacacacabacacabacacacacacabacacabacacacacacabacacabacacacacacabacacabacacacacacabacacabacacacacacabacacabacacacacacabacacabacacacacacabacacabacacacacacabacacabacacacacacabacacabacacac
acacabacacabacacac
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbpppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
a
stdout
copy 
Case 1: 1
Case 2: 1
Case 3: 2
Case 4: 0
Case 5: 315
https://ideone.com/dxJXCu
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!