Advertisement
Guest User

Untitled

a guest
Oct 20th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.15 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include "optimization.h"
  5. using namespace std;
  6.  
  7. char s[100000];
  8. vector<long long> hashs, p;
  9. long long mod = 9223372036854775783;
  10. long long len = 0;
  11.  
  12. void myHash () {
  13. long long result = 0;
  14. p[0] = 1;
  15. for(long long i = 1; i < len; i++) {
  16. p[i] = (p[i-1] * 67) % mod;
  17. }
  18. hashs[0] = s[0];
  19. for (long long i = 1; i < len; i++) {
  20. hashs[i] = (hashs[i-1] + (s[i]*p[i])%mod) % mod;
  21. }
  22. }
  23.  
  24.  
  25. int main() {
  26. //freopen ("1.txt", "r", stdin);
  27. s[len] = getChar();
  28. while (s[len] >= 'a' && s[len] <= 'z') {
  29. len++;
  30. s[len] = getChar();
  31. }
  32. long long n = readInt();
  33. long long l1, r1, l2, r2;
  34.  
  35. hashs.resize(len);
  36. p.resize(len);
  37. myHash();
  38.  
  39. for (long long i = 0; i < n; i ++) {
  40. l1 = readInt() - 1;
  41. r1 = readInt() - 1;
  42. l2 = readInt() - 1;
  43. r2 = readInt() - 1;
  44. if (l1 > l2) {
  45. swap(l1, l2);
  46. swap(r1, r2);
  47. }
  48. long long h1 = hashs[r1];
  49. if (l1) h1 = (h1 - hashs[l1-1] + mod) % mod;
  50.  
  51. long long h2 = hashs[r2];
  52. if (l2) h2 = (h2 - hashs[l2-1] + mod) % mod;
  53.  
  54. if ((h1 * p[l2-l1]) % mod == h2){
  55. writeWord("Yes\n");
  56. }
  57. else {
  58. writeWord("No\n");
  59. }
  60. }
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement