Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.2 kB
4
Indexable
Never
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const long long int MOD = 1e9+7;
const int b = 47;

vector<long long int> h;
vector<long long int> pw;

int sub(int a, int b) {
    if (a - b < 0) {
        return a - b + MOD;
    } else {
        return a - b;
    }
}

int add(int a, int b) {
    if (a + b >= MOD) {
        return a + b - MOD;
    } else {
        return a + b;
    }
}

long long int mul(int a, int b) {
    return 1ll * a * b % MOD;
}

void power(int n) {
    pw.push_back(1);
    for (int i=1; i <= n; i++) {
        pw.push_back(mul(pw[i-1], b));
    }
}

void build_hash(string &s) {
    h.push_back(0);
    for (int i=1; i <= s.size(); i++) {
        h.push_back(add(mul(h[i - 1], b), (s[i - 1] - 'a' + 1)));
    }
}


int get_hash(string &s, int l, int r) {
    return sub(h[r], mul(h[l], pw[r - l]));
}

int main() {
    string s;
    int m, l1, r1, l2, r2;
    cin >> s >> m;
    build_hash(s);
    power(s.size() + 2);
    for (int i=0; i < m; i++) {
        cin >> l1 >> r1 >> l2 >> r2;
        if (get_hash(s, l1, r1) == get_hash(s, l2, r2)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}