字符串哈希

注意p数组保存的是p的几次幂的值；
h数组保存的是字符串从位置1开始到i的字符串的哈希值

#include<iostream>
using namespace std;
const int N=100005;
const int P=13331;
int h[N],p[N];

int main(){
    int n,m;
    cin>>n>>m;
    string a;
    cin>>a;
    p[0]=1;
    h[0]=0;
    // 字符串转换为哈希值存储
    for(int i=0;i<a.size();i++){
        p[i+1] = p[i] * P;
        h[i+1]=h[i]*P+a[i];
    }
    int l1,r1,l2,r2;
    while(m--){
        cin>>l1>>r1>>l2>>r2;
        if(h[r1]-h[l1-1]*p[r1-l1+1] == h[r2]-h[l2-1]*p[r2-l2+1]) puts("Yes");
        else puts("No");
    }
    return 0;
}