Untitled
unknown
plain_text
3 years ago
1.1 kB
6
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...