A1665 兔子与兔子

// A1665 兔子与兔子 —— 字符串哈希（子串相等判定）
//
// 每次询问两个区间是否完全相同。|S|、m 都可达 1e6，不能逐字符比较。
//
// 做法：预处理前缀哈希 h[i] = h[i-1] * B + c_i（模 P），
//       区间 [l, r] 的哈希 = h[r] - h[l-1] * B^(r-l+1)，
//       于是每个询问 O(1) 得到两个区间的哈希并比较。
// 为了把碰撞概率压到极低，同时再算一份 64 位自然溢出哈希，两份都相等才判相同。
// 另外长度不同的两个区间直接判不同。

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;

const ll MOD = 1000000007LL;
const ll BASE = 131LL;
const ull UBASE = 13331ULL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = (int)s.size();

    vector<ll> h(n + 1, 0), pw(n + 1, 1);        // 模 P 的前缀哈希与幂
    vector<ull> hu(n + 1, 0), pu(n + 1, 1);       // 64 位自然溢出哈希与幂
    for (int i = 1; i <= n; i++) {
        ll c = s[i - 1] - 'a' + 1;
        h[i] = (h[i - 1] * BASE + c) % MOD;
        pw[i] = pw[i - 1] * BASE % MOD;
        hu[i] = hu[i - 1] * UBASE + (ull)c;
        pu[i] = pu[i - 1] * UBASE;
    }

    int m;
    cin >> m;
    while (m--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        int len = r1 - l1 + 1;
        if (len != r2 - l2 + 1) { // 长度不同，必然不同
            cout << "No\n";
            continue;
        }
        ll a = (h[r1] - h[l1 - 1] * pw[len] % MOD + MOD) % MOD;
        ll b = (h[r2] - h[l2 - 1] * pw[len] % MOD + MOD) % MOD;
        ull ua = hu[r1] - hu[l1 - 1] * pu[len];
        ull ub = hu[r2] - hu[l2 - 1] * pu[len];
        cout << ((a == b && ua == ub) ? "Yes\n" : "No\n");
    }
    return 0;
}