Untitled
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; }