字符串哈希

注意点
1. 字符串下标从1开始
2. P=131， mod = 2^64，这里用ULL，自动溢出

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, P = 131;
typedef unsigned long long ULL;

char s[N];
ULL p[N], h[N];


ULL get(int l, int r) {  //求一段字符串的哈希值
    return h[r] - h[l - 1] * p[r - l + 1];
}


int main() {
    int n, m;
    cin >> n >> m;
    scanf("%s", s + 1);  //⚠️

    p[0] = 1;
    for (int i = 1; i <= n; i++) {  //从字符串的第一位开始算
        p[i] = p[i - 1] * P;  //p[i]表示p的i次方，get中要用
        h[i] = h[i - 1] * P + s[i];//当前一位到字符串首的哈希值=前一位的哈希值乘P+当前字符串值(第0位)
    }
    while (m--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}