F02 字符串哈希

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 1110000;
const ULL P = 131, mod = 1000000007;
char s[N];

ULL f[N], d[N];
int main()
{
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    d[0] = 1;
    for (int i = 1; i <= len; i++)
    {
        f[i] = (f[i - 1] * 131 + (s[i] - 'a' + 1));
        d[i] = d[i - 1] * 131;
    }
    int T; scanf("%d", &T);
    while (T--)
    {
        int l1, r1, l2, r2; scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (f[r1] - f[l1 - 1] * d[r1 - l1 + 1] == f[r2] - f[l2 - 1] * d[r2 - l2 + 1]) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}