Advertisement
Guest User

Untitled

a guest
Feb 20th, 2020
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef long long ll;
  7. //typedef int ll;
  8. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  9. ll MAX = 1e15;
  10.  
  11. vector<ll> hashes;
  12. vector<ll> pows;
  13. //resent
  14.  
  15.  
  16. int main() {
  17.     ios_base::sync_with_stdio(0);
  18.     freopen("substrcmp.in", "r", stdin);
  19.     freopen("substrcmp.out", "w", stdout);
  20.  
  21.     string s;
  22.     cin >> s;
  23.     ll n = s.size();
  24.     hashes.resize(n);
  25.     pows.resize(n+1);
  26.     ll p = 31;
  27.     pows[0]=1;
  28.     for(ll i=1; i<=n; i++){
  29.         pows[i]=pows[i-1]*p;
  30.     }
  31.     hashes[0]=s[0];
  32.     for(ll i=1; i<n; i++){
  33.         hashes[i] = hashes[i-1]+s[i]*pows[i];
  34.     }
  35.     ll q;
  36.     cin >> q;
  37.     while(q--){
  38.         ll a,b,c,d;
  39.         cin >> a >> b >> c >> d;
  40.         a--;
  41.         b--;
  42.         c--;
  43.         d--;
  44.         ll hash1, hash2 = 0;
  45.         if(a==0){
  46.             hash1 = hashes[b];
  47.         }
  48.         else {
  49.             hash1 = hashes[b]-hashes[a-1];
  50.         }
  51.  
  52.         if(c==0){
  53.             hash2 = hashes[d];
  54.         }
  55.         else {
  56.             hash2 = hashes[d]-hashes[c-1];
  57.         }
  58.         hash1 = hash1 * pows[n-a];
  59.         hash2 *= pows[n-c];
  60.         if(hash1==hash2){
  61.             cout << "Yes\n";
  62.         }
  63.         else{
  64.             cout << "No\n";
  65.         }
  66.  
  67.     }
  68.  
  69.  
  70.  
  71.  
  72.  
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement