Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("Ofast")
- //#pragma GCC optimize("unroll-loops")
- //#pragma GCC target("sse,sse2,ssse3,sse3,sse4,avx,avx2,popcnt,tune=native")
- #include <iostream>
- #include <vector>
- #include <string>
- #include <queue>
- #include <set>
- #include <iomanip>
- #include <map>
- #include <algorithm>
- #include <cmath>
- #include <bitset>
- #include <limits.h>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- #define all(x) (x).begin(),(x).end()
- #define pii pair<int, int>
- #define sz(x) (int)x.size()
- const ll o = 31, MOD1 = 1000 * 1000 * 1000 + 33, MOD2 = 1000 * 1000 * 1000 + 9;
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- string s;
- cin >> s;
- int n = sz(s);
- vector<ll> pf(n + 1, 1), ps(n + 1, 1);
- for (int i = 1; i <= n; ++i) {
- pf[i] = (pf[i - 1] * o) % MOD1;
- ps[i] = (ps[i - 1] * o) % MOD2;
- }
- vector<ll> hf(n), hs(n);
- hf[0] = (ll)(s[0] - 'a' + 1);
- hs[0] = (ll)(s[0] - 'a' + 1);
- for (int i = 1; i < n; ++i) {
- hf[i] = (hf[i - 1] + (ll)(s[i] - 'a' + 1) * pf[i]) % MOD1;
- hs[i] = (hs[i - 1] + (ll)(s[i] - 'a' + 1) * ps[i]) % MOD2;
- }
- int k;
- cin >> k;
- for (int i = 0; i < k; ++i) {
- int l1, r1, l2, r2;
- cin >> l1 >> r1 >> l2 >> r2;
- --l1; --r1; --l2; --r2;
- if (r1 - l1 != r2 - l2) {
- cout << "No\n";
- }
- else {
- ll h1 = (hf[r1] - (l1 == 0 ? 0 : hf[l1 - 1]) + MOD1) % MOD1,
- h2 = (hf[r2] - (l2 == 0 ? 0 : hf[l2 - 1]) + MOD1) % MOD1;
- h1 = (h1 * (l2 <= l1 ? 1 : pf[l2 - l1])) % MOD1;
- h2 = (h2 * (l1 <= l2 ? 1 : pf[l1 - l2])) % MOD1;
- ll h3 = (hs[r1] - (l1 == 0 ? 0 : hs[l1 - 1]) + MOD2) % MOD2,
- h4 = (hs[r2] - (l2 == 0 ? 0 : hs[l2 - 1]) + MOD2) % MOD2;
- h3 = (h3 * (l2 <= l1 ? 1 : ps[l2 - l1])) % MOD2;
- h4 = (h4 * (l1 <= l2 ? 1 : ps[l1 - l2])) % MOD2;
- cout << (h1 == h2 && h3 == h4 ? "Yes\n" : "No\n");
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement