Advertisement
Guest User

Untitled

a guest
Apr 2nd, 2020
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8. string s;
  9. cin >> s;
  10.  
  11. const int p = 31;
  12. vector<long long> p_pow(s.length());
  13. p_pow[0] = 1;
  14. for (size_t i = 1; i < p_pow.size(); ++i)
  15. p_pow[i] = p_pow[i - 1] * p;
  16.  
  17. vector<long long> h(s.length());
  18. for (size_t i = 0; i < s.length(); ++i) {
  19. h[i] = (s[i] - 'a' + 1) * p_pow[i];
  20. if (i) h[i] += h[i - 1];
  21. }
  22.  
  23. int m;
  24. cin >> m;
  25. for (int i = 0; i < m; ++i) {
  26. int l1, r1, l2, r2;
  27. cin >> l1 >> r1 >> l2 >> r2;
  28. l1--;
  29. r1--;
  30. l2--;
  31. r2--;
  32.  
  33. int len = r1 - l1 + 1;
  34. int len2 = r2 - l2 + 1;
  35.  
  36. if (len != len2) {
  37. cout << "No" << endl;
  38. continue;
  39. }
  40.  
  41. long long h1 = h[l1 + len - 1];
  42. if (l1)
  43. h1 -= h[l1 - 1];
  44.  
  45. long long h2 = h[l2 + len - 1];
  46. if (l2)
  47. h2 -= h[l2 - 1];
  48.  
  49. if (l1 <= l2 && h1 * p_pow[l2 - l1] == h2 ||
  50. l1 > l2 && h1 == h2 * p_pow[l1 - l2])
  51. cout << "Yes" << endl;
  52. else
  53. cout << "No" << endl;
  54. }
  55. return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement