思路(字丑勿喷)

代码

有注释

#include <iostream>

using namespace std;

const int N = 100010;

/*
* p[] : 存放次方数，h[r] - h[l - 1] * P ^ R - L + 1, 后面的次方不好处理，所以放到数组中
* h[] : 存放字符串的前缀值
* P   : 经验值 131 or 13331，不容易哈希冲突
*/

typedef unsigned long long ull; // ull 是 2 ^ 64 - 1 ，这样转换为 p 进制数之后就不需要 mod 了，溢出就是自动 mod

ull h[N], p[N];
char str[N];
int P = 131, n, m;

ull get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1]; // 公式，背住 本质是把 l - 1 提高到相应位数进行运算，得到的就是区间的哈希值
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    // 从 1 开始
    cin >> n >> m >> str + 1;

    p[0] = 1; // 一定为 1 否则预处理 p[] 时出错
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i]; // 类比前缀和 ，将数字转换为 P 进制
    }

    while (m -- ) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (get(l1, r1) == get(l2, r2)) {
            puts("Yes");
        } else {
            puts("No");
        }
    }

    return 0;
}

无注释

#include <iostream>

using namespace std;

const int N = 100010;

typedef unsigned long long ull;

char str[N];
ull p[N], h[N];
int n, m, P = 131;

ull get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> str + 1;

    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }

    while (m -- ) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (get(l1, r1) == get(l2, r2)) {
            puts("Yes");
        } else {
            puts("No");
        }
    }

    return 0;
}