题目描述
给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1]和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n 和 m，表示字符串长度和询问次数。
第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。
接下来 mm 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。
注意，字符串的位置从 1 开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤105
输入样例
输入数据 1
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2输出数据 1
Yes
No
Yes前置知识：有三种，自然溢出，单
，双
。
- 自然溢出：我们定义base，而MOD对于自然溢出方法，就是 unsigned long long 整数的自然溢出（相当于MOD 是
)
- 单hash：我们定义base和mod，有了对应的要求余MOD，一般用long long，对应的hash公式为
双:用字符串Hash，最怕的就是，出现冲突的情况，即不同字符串却有着相同的hash值，这是我们不想看到的。所以为了降低冲突的概率，可以用双Hash方法。
将一个字符串用不同的Base和MOD，hash两次，将这两个结果用一个二元组表示，作为一个总的Hash结果。那么公式为
对于截取范围内的字符串，公式为
#include <bits/stdc++.h>
using namespace std;
#define accelerate ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define int long long
#define mod 1000000007
#define ll unsigned long long
#define PII pair<int,int>
#define INF 0x3f3f3f3f
const int N=1e5+10;
const int base=29;
int n,m,k,x,y,T,xx,yy;
int hashh[N],p[N];
char a[N];
int getnum(int x,int y){
return hashh[y]-hashh[x-1]*p[y-x+1];
}
signed main(){
accelerate;
cin>>n>>m;
cin>>a+1;
p[0]=1;
for(int i=1;i<=n;i++){
p[i]=p[i-1]*base;
hashh[i]=hashh[i-1]*base+(a[i]-'a'+1);
}
while(m--){
cin>>x>>y>>xx>>yy;
if(getnum(x,y)==getnum(xx,yy)) cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}