Advertisement
Guest User

Untitled

a guest
Feb 28th, 2020
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5. string s;
  6. size_t n, a, b, c, d;
  7. vector<long long> prefix;
  8. vector<long long> prefix1;
  9. long long prime =  80630964769;
  10. long long prime1 = 63018038201;
  11. long long x = 19;
  12. long long x1 = 31;
  13.  
  14. int main() {
  15.     cin >> s;
  16.     prefix.resize(s.size() + 1);
  17.     prefix1.resize(s.size() + 1);
  18.     cin >> n;
  19.     prefix[1] = (s[0] - 'a');
  20.     prefix1[1] = (s[0] - 'a');
  21.     for (size_t i = 2; i <= s.size(); ++i) {
  22.         // cout << (s[i - 1] - 'a') << endl;
  23.         prefix[i] = (prefix[i - 1] * x + (s[i - 1] - 'a')) % prime;
  24.         prefix1[i] = (prefix1[i - 1] * x1 + (s[i - 1] - 'a')) % prime1;
  25.     }
  26.     for (size_t i = 0; i < n; ++i) {
  27.         cin >> a >> b >> c >> d;
  28. //        cout << prefix[b] << endl;
  29. //        cout << prefix[a - 1] * (int) pow(x, b - a + 1) % prime << endl;
  30. //        cout << prefix[d] << endl;
  31. //        cout << prefix[c - 1] * (int) pow(x, b - a + 1) % prime << endl;
  32.         if ((b - a != d - c)
  33.         || (prefix[b] - ((prefix[a - 1] * (long long) pow(x, b - a + 1)) % prime)
  34.         != (prefix[d] - ((prefix[c - 1] * (long long) pow(x, d - c + 1)) % prime)))
  35.         || (prefix1[b] - ((prefix1[a - 1] * (long long) pow(x1, b - a + 1)) % prime1)
  36.         != (prefix1[d] - ((prefix1[c - 1] * (long long) pow(x1, d - c + 1)) % prime1)))) {
  37.             cout << "No" << '\n';
  38.         } else {
  39.             cout << "Yes" << '\n';
  40.         }
  41.     }
  42.     return 0;
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement