Untitled
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...