Advertisement
Guest User

Untitled

a guest
May 6th, 2015
238
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.10 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <iomanip>
  4. #include <cmath>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <fstream>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <deque>
  12. #include <cmath>
  13. #include <algorithm>
  14. #include <time.h>
  15.  
  16. using std::cin;
  17. using std::cout;
  18. using std::endl;
  19. using std::vector;
  20. using std::string;
  21. using std::pair;
  22. using std::make_pair;
  23. using std::set;
  24. using std::map;
  25. using std::queue;
  26. using std::ifstream;
  27. using std::ofstream;
  28. using std::min;
  29. using std::max;
  30. using std::ios_base;
  31.  
  32. vector< int > h;
  33. vector< int > p;
  34.  
  35. void hash_code(string s)
  36. {
  37. h.resize(s.size());
  38. p.resize(s.size());
  39. h[0] = s[0];
  40. p[0] = 1;
  41. for (size_t i = 1; i != s.size(); ++i)
  42. {
  43. p[i] = p[i - 1] * 239;
  44. h[i] = h[i - 1] + s[i] * p[i];
  45. }
  46. // for (size_t i = 0; i != p.size(); ++i)
  47. // cout << h[i] << ' ' << p[i] << endl;
  48. }
  49.  
  50. int main()
  51. {
  52. ifstream in("substrcmp.in");
  53. ofstream out("substrcmp.out");
  54. srand (time(NULL));
  55. string s;
  56. in >> s;
  57. hash_code(s);
  58. int n = 0;
  59. in >> n;
  60. for (int i = 0; i != n; ++i)
  61. {
  62. int a = 0;
  63. int b = 0;
  64. int c = 0;
  65. int d = 0;
  66. in >> a >> b >> c >> d;
  67. --a; --b; --c; --d;
  68. int ha = (a == 0 ? 0 : h[a - 1]);
  69. int hc = (c == 0 ? 0 : h[c - 1]);
  70. if ((h[b] - ha) * p[c] == (h[d] - hc) * p[a] && b - a == d - c)
  71. {
  72. if (b == a)
  73. {
  74. if (s[b] == s[c])
  75. out << "Yes" << endl;
  76. else
  77. out << "No" << endl;
  78. continue;
  79. }
  80. int delta = 0;
  81. if (b - a > 7)
  82. for (int j = 0; j != 15; ++j)
  83. {
  84. delta = rand() % (b - a);
  85. if (s[a + delta] != s[c + delta])
  86. {
  87. out << "No" << endl;
  88. delta = -1;
  89. break;
  90. }
  91. }
  92. if (delta == -1)
  93. continue;
  94. out << "Yes" << endl;
  95. }
  96. else
  97. out << "No" << endl;
  98. }
  99.  
  100. return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement