Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <iomanip>
- #include <cmath>
- #include <cstdlib>
- #include <cstdio>
- #include <fstream>
- #include <set>
- #include <map>
- #include <queue>
- #include <deque>
- #include <cmath>
- #include <algorithm>
- #include <time.h>
- using std::cin;
- using std::cout;
- using std::endl;
- using std::vector;
- using std::string;
- using std::pair;
- using std::make_pair;
- using std::set;
- using std::map;
- using std::queue;
- using std::ifstream;
- using std::ofstream;
- using std::min;
- using std::max;
- using std::ios_base;
- vector< int > h;
- vector< int > p;
- void hash_code(string s)
- {
- h.resize(s.size());
- p.resize(s.size());
- h[0] = s[0];
- p[0] = 1;
- for (size_t i = 1; i != s.size(); ++i)
- {
- p[i] = p[i - 1] * 239;
- h[i] = h[i - 1] + s[i] * p[i];
- }
- // for (size_t i = 0; i != p.size(); ++i)
- // cout << h[i] << ' ' << p[i] << endl;
- }
- int main()
- {
- ifstream in("substrcmp.in");
- ofstream out("substrcmp.out");
- srand (time(NULL));
- string s;
- in >> s;
- hash_code(s);
- int n = 0;
- in >> n;
- for (int i = 0; i != n; ++i)
- {
- int a = 0;
- int b = 0;
- int c = 0;
- int d = 0;
- in >> a >> b >> c >> d;
- --a; --b; --c; --d;
- int ha = (a == 0 ? 0 : h[a - 1]);
- int hc = (c == 0 ? 0 : h[c - 1]);
- if ((h[b] - ha) * p[c] == (h[d] - hc) * p[a] && b - a == d - c)
- {
- if (b == a)
- {
- if (s[b] == s[c])
- out << "Yes" << endl;
- else
- out << "No" << endl;
- continue;
- }
- int delta = 0;
- if (b - a > 7)
- for (int j = 0; j != 15; ++j)
- {
- delta = rand() % (b - a);
- if (s[a + delta] != s[c + delta])
- {
- out << "No" << endl;
- delta = -1;
- break;
- }
- }
- if (delta == -1)
- continue;
- out << "Yes" << endl;
- }
- else
- out << "No" << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement