给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2，请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式
第一行包含整数n和m，表示字符串长度和询问次数。

第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。

接下来m行，每行包含四个整数l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从1开始编号。

输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。

每个结果占一行。

数据范围
1≤n,m≤105
输入样例：

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例：

Yes
No
Yes

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,P=131;
typedef unsigned long long ull;
char str[N];
int n,m,l1,r1,l2,r2;
ull h[N],p[N];
ull get(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}
int main(){
    cin>>n>>m>>str+1;
    p[0]=1;
    for(int i=1;i<=n; i++){
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+str[i];
    }
    while(m--){
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2))puts("Yes");
        else puts("No");
    }
    return 0;
}

字符串前缀哈希法:

例:
str=="ABCABCDEWUZGNMACWING"
h[0]=0
h[1]="A"的哈希值
h[2]="AB"的哈希值
h[3]="ABC"的哈希值
h[4]="ABCD"的哈希值
   ······
预处理所有出来前缀的哈希值
问题1:如何定义某前缀的哈希值？
例：求"A B C D"的哈希值
公式：h[i]=h[i-1]*P+str[i];
(1)把它看成P进制的数，有四位，第1位里的数是A，第2位里的数是B，第3位里的数是C，第4位里的数是D（从左边数）。
假设只有大写字母"A"~"Z"
A B C D E ...... Z
1 2 3 4 5 ...... 26
ABCD=P进制的1234
再把它转成十进制
(1*p^3+2*p^2+3*p^1+4*p^0)
因为会非常大，所以需要%Q来把一个字符串映射成一个从0~q-1的一个数
注意：
（1）不可以把-个字母映射成0
例:
   A=0
  AA=0                  冲突
 AAA=0
AAAA=0
......
哈希数字可存在冲突，
哈希字符串不存在冲突。
经验值：
p=131或13331
Q=2的六十四次方
99.99%不冲突
哈希前缀的好处：用它可以求出来任意一个子串的哈希值
已知：
L
R
H[R]    1~R的哈希值
h[l-1]  1~L-1的哈希值
公式：h[r]-h[l-1]*p[r-l+1];
求两段哈希值，如果哈希值相同，认为字符串就相同，如果哈希值不同，认为字符串就不同