基础知识

y总已经给了P=131 or p=1331
进制转换 ABCD 1001 对比看
式子：1* 2^3+ 0* 2^2+ 0* 2^1+ 1* 2^0
同理：A* P^3+ B* P^2+ C* P^1+ D* P^0
区间那个式子是 h[r]-h[l-1]*p[r-l+1];

解释

h[i]=h[i-1]*P+str[i]==进制转换
比如：
1234 
h[1]=0*P+1      h[0]=0
h[2]=h[1]*P+2   h[1]=1
h[3]=h[2]*P+3   h[2]=P+2
h[4]=h[3]*P+4   h[3]=1*P^2+2*P+3;
                h[4]=1*P^3+2*P^2+3 *P+4

C++代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10,P=131;
typedef unsigned long long ull;
int n,m;
char str[N];
ull p[N],h[N],p[0]=1;
ull ce(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main ()
{
    scanf("%d%d%s",&n,&m,str+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;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(ce(l1,r1)==ce(l2,r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}