AcWing 841. 字符串哈希
原题链接
简单
作者:
尼古拉斯小布丁
,
2021-08-22 17:37:47
,
所有人可见
,
阅读 203
/*
AcWing 841. 字符串哈希
字符串是从序号为1的位置开始读取
*/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ULL;
const int N =100005, P=131;
ULL h[N], p[N];
char str[N];
int n,m;
ULL get(int l, int r){
return h[r]-h[l-1]*p[r-l+1]; //某一区间字符串前缀的哈希值公式
}
int main(){
scanf("%d%d%s", &n, &m, str+1);
p[0]=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];
}
int l1, r1, l2, r2;
while(m--){
scanf("%d%d%d%d",&l1, &r1, &l2, &r2);
if(get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}