Advertisement
PALI_nka

Untitled

Oct 1st, 2020
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <fstream>
  5. #include <iostream>
  6. #include <unordered_set>
  7. #include <random>
  8. unsigned long long h[100001], deg[100001];
  9.  
  10. void makeHash(std::string s, int n, unsigned long long P) {
  11.     h[0] = 0;
  12.     deg[0] = 1;
  13.     for (int i = 0; i < n; i++) {
  14.         h[i + 1] = h[i] * P + s[i];
  15.         deg[i + 1] = deg[i] * P;
  16.     }
  17. }
  18.  
  19. unsigned long long getHash(const std::string&, int st, int end) {
  20.     return h[end] - h[st] * deg[end - st];
  21. }
  22.  
  23. int main() {
  24.     std::ios_base::sync_with_stdio(false);
  25.     std::cin.tie(0);
  26.  
  27.     std::random_device rd;
  28.     std::mt19937 gen(rd());
  29.     std::uniform_int_distribution<long long int> distr(INTMAX_MAX, UINTMAX_MAX);
  30.     const unsigned long long P = distr(gen);
  31.  
  32.     int M;
  33.     std::string str;
  34.     std::cin >> str >> M;
  35.  
  36.     makeHash(str, str.size(), P);
  37.  
  38.     for (int i = 0; i < M; i++) {
  39.         int a, b, c, d;
  40.         std::cin >> a >> b >> c >> d;
  41.         if (((b - a) == (d - c)) && getHash(str.substr(a - 1, b - a + 1), a - 1, b) == getHash(str.substr(c - 1, d - c + 1), c - 1, d)) std::cout << "Yes\n";
  42.         else std::cout << "No\n";
  43.     }
  44.     return 0;
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement