字符串哈希常用于字符串匹配的问题中，用$O(1)$的复杂度暴力求解。

这里使用的哈希算法(BKDRHash)思想就是将字符串转换为一个131进制数(至于为什么是这个数可以参考拓展参考)，并求前缀和取模，即

$$sum(x)=\sum_{i=1}^{x-1}\limits sum(i)+p_{x}\ (mod\ m)$$

预处理的复杂度是$O(n)$，我们通过比较$sum(r)-sum(l-1)*131^{r-l+1}(mod\ m)$就可以知道两个子串是否相等了。

值得一提的是，这样写是有错误率的，即哈希碰撞的现象，常见的处理方式包括建链表等，这里就不继续深入讨论了。

给出参考代码

#include <bits/stdc++.h>
#define f(a,b,c) for(int a=b;a<c;++a)
#define MAXN 1000001
using namespace std;

string s;
unsigned long long h[MAXN],p[MAXN];
int m;

int main() {
    cin >> s >> m;

    int cnt = 1;
    p[0] = 1;
    for(char x : s) {
        h[cnt] = h[cnt - 1] * 131 + (x - 'a' + 1) ;
        p[cnt] = p[cnt - 1] * 131;
        ++cnt;
    }

    int r1,l1,r2,l2;
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);

        if(h[r1] - h[l1 - 1] * p[r1 - l1 + 1] == h[r2] - h[l2 - 1] * p[r2 - l2 + 1])
            printf("Yes\n");
        else
            printf("No\n");
    }

    return 0;
}

由于用的是无符号长整型，溢出后就相当于自动取模了，而模数即$2^{64}-1$。

数据量有点大，尽量不要用C++的流操作（cin cout是真的慢）。

拓展参考：[https://blog.csdn.net/wanglx_/article/details/40400693]