python/TangDou/AcWing/138.cpp

#include <bits/stdc++.h>

using namespace std;

//省代码写法
typedef unsigned long long ULL;

const int N = 1000010, P = 131; //经验 或者 13331，取这两值的冲突概率低

int m;
char str[N];    //字符串
ULL h[N], p[N]; //h表示某一个前缀的HASH值,h[k]表示的是前k个字母的HASH值,p[k]存储P^k mode 2^64

//计算部分字符串的HASH值
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

//模板裸题啊！

int main() {
    //输入+输出重定向
    freopen("../AcWing/N6/138.txt", "r", stdin);
    //计算字符串前缀的HASH值，就是预处理
    scanf("%s%d", str + 1, &m);
    //预处理
    p[0] = 1;
    int n = strlen(str + 1);//因为我们把字符串放的时候放弃了索引0，所以这里strlen就也需要躲开0.
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }
    //然后根据公式计算两个区间的字符串HASH值是不是相同
    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");
    }

    //关闭文件
    fclose(stdin);
    return 0;
}