C 代码

//本题使用的字符串哈希方法有3个注意点
//1.在映射时，不能将某一个字母映射成0,会引发冲突
//2.这种方法是有可能产生冲突的，只是概率较小
//3.取经验值sys(进制) = 131 或者 13331 ,mod = 2^64 时，冲突的概率最小

#include <stdio.h>
#include <string.h>

typedef unsigned long long ULL;

#define N 100010

//取131进制
int sys = 131;

//字符串的前缀数组
//h[0]=0,h[1]=a的值对应的p进制数，h[2]=aa对应的p进制数,以此类推
//用unsigned long long 来存，如果数字溢出，从0开始重新记，相当于对数字取2^64模
ULL h[N],p[N];          
//p[i]用来预处理p的i次方，使用时可以直接取用，不用再计算
//并且由于之后p[i]要与另一个数字相乘后取模，故直接用ULL来存，溢出则相当于提前取模
//即 y * (mod + x) % mod = (y * mod + y * x) % mod = (y * x) % mod ,提前取模是没有问题的

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    //sys的0次方等于1
    p[0] = 1; 

    getchar();   //吃回车

    for (int i=1;i<=n;i++){
        //空字符/0的值才为0，用getchar保证了不会有字符被映射为0
        h[i] = h[i-1]*sys + getchar();
        p[i] = p[i-1]*sys;
    }
    while (m--){
       int l1,r1,l2,r2;
       scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
       ULL s1,s2;
       //这里我们本来需要的是s1 = (1到r1这段字符串对应的sys进制值  -  1到l1-1段对应的sys进制值*p[r1-l1+1]) % mod
       //但是我们手中只有被取过模后的数据h[r1] 和 h[l1 - 1]
       //根据差的余数等于余数的差  (a-b)%mod = a%mod - b%mod
       //可以转化为s1 = h[r1] - h[l1-1]*p[r1-l1+1];
       s1 = h[r1] - h[l1-1]*p[r1-l1+1];
       s2 = h[r2] - h[l2-1]*p[r2-l2+1];
       if (s1 == s2) printf("Yes\n");
       else printf("No\n");
    }
}