fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void solve(){
  5.     string s, p;
  6.     cin>>s>>p;
  7.     int q;
  8.     cin>>q;
  9.  
  10.     int n = s.length(), m = p.length();
  11.     int pow = 31;
  12.     int mod = 1e9 + 7;
  13.  
  14.     vector<long long> pp(n);
  15.     pp[0] = 1;
  16.  
  17.     for(int i = 1; i < n; i++){
  18.         pp[i] = (pp[i-1]*pow)%mod;
  19.     }
  20.  
  21.     vector<long long> hs(n + 1);
  22.     hs[0] = 0;
  23.  
  24.     for(int i = 0; i < n; i++){
  25.         hs[i+1] = (hs[i] + (s[i] - 'a' + 1)*pp[i])%mod;
  26.     }
  27.  
  28.     long long hp = 0;
  29.  
  30.     for(int i = 0; i < m; i++){
  31.         hp = (hp + (p[i] - 'a' + 1)*pp[i])%mod;
  32.     }
  33.  
  34.     while(q--){
  35.         int a, b;
  36.         cin>>a>>b;
  37.  
  38.         int i = a;
  39.         int cnt = 0;
  40.  
  41.         while(i +  m <= b + 1){
  42.             long long sstrh = (hs[i + m] - hs[i] + mod)%mod;
  43.             long long tph = (hp * pp[i])%mod;
  44.             if(tph == sstrh){
  45.                 cnt++;
  46.                 i += m;
  47.             }
  48.             else{
  49.                 i++;
  50.             }
  51.         }
  52.         cout<<cnt<<endl;
  53.     }
  54. }
  55.  
  56. int main()
  57. {
  58.     long long t;
  59.     cin >> t;
  60.     for(int it=1;it<=t;it++) {
  61.      cout << "Case " << it << ":"<<endl;
  62.         solve();
  63.     }
  64.     return 0;
  65. }
  66.  
  67.  
  68.  
Success #stdin #stdout 0s 5544KB
comments (?)
stdin
copy 
1
abababc
ab
3
0 6
1 2
0 4
stdout
copy 
Case 1:
3
0
2
https://ideone.com/4Q6muI
language:
C++ (gcc 8.3)
created:
3 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!