Untitled

 avatar
unknown
plain_text
2 years ago
1.1 kB
4
Indexable
#include <iostream>
#include <vector>
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 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;
        r1++;r2++;
        if (get_hash(s,l1,r1) == get_hash(s,l2,r2)){
            cout<<"Yes"<<endl;
        } else {
            cout<<"No"<<endl;
        }
    }
    return 0;
}
Editor is loading...