Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const int mod = 1e9 + 7;
- const int p1 = 59, p2 = 239;
- vector<ll> h1, deg1;
- vector<ull> h2, deg2;
- ll get_hash1(int l, int r) {
- return ((h1[r] - h1[l] * deg1[r - l]) % mod + mod) % mod;
- }
- ull get_hash2(int l, int r) {
- return h2[r] - h2[l] * deg2[r - l];
- }
- bool equal(int l1, int r1, int l2, int r2) {
- return get_hash1(l1 - 1, r1) == get_hash1(l2 - 1, r2) and
- get_hash2(l1 - 1, r1) == get_hash2(l2 - 1, r2);
- }
- int main() {
- string s;
- cin >> s;
- int n = sz(s);
- deg1.resize(n + 1, 1); deg2.resize(n + 1, 1); h1.resize(n + 1); h2.resize(n + 1);
- for (int i = 0; i < sz(s); ++i) {
- deg1[i + 1] = deg1[i] * p1 % mod;
- deg2[i + 1] = deg2[i] * p2;
- h1[i + 1] = (h1[i] * p1 + s[i]) % mod;
- h2[i + 1] = h2[i] * p2 + s[i];
- }
- int q;
- cin >> q;
- while (q--) {
- int l1, l2, r1, r2;
- cin >> l1 >> r1 >> l2 >> r2;
- int l = -1, r = min(r1 - l1, r2 - l2) + 1;
- while (r - l > 1) {
- int m = l + r >> 1;
- if (equal(l1, l1 + m, l2, l2 + m)) {
- l = m;
- } else {
- r = m;
- }
- }
- if (l == max(r1 - l1, r2 - l2)) {
- cout << "=\n";
- } else if (l == r2 - l2) {
- cout << ">\n";
- } else if (l == r1 - l1) {
- cout << "<\n";
- } else {
- cout << (s[l1 + l] > s[l2 + l] ? ">" : "<") << '\n';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement