AcWing 841. 字符串哈希
原题链接
简单
作者:
Yolo_28
,
2021-12-06 17:43:18
,
所有人可见
,
阅读 108
#include<iostream>
using namespace std;
typedef unsigned long long ull;//mod取2^64即unsigned long long冲突会很小
const int N = 100010,P= 131;//base进制P一般取131或13331 冲突会很小
int n,m;
char str[N];
ull h[N],p[N];//直接定义为ull类型,不用取模(溢出相当于取模)
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;
for(int i = 1;i<=n;i++){
p[i] = p[i-1]*P;
h[i] = h[i-1]*P + str[i];//Hash公式:(h[i] = h[i-1]*P + str[i]) mod Q
}
while(m--){
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(get(l1,r1) ==get(l2,r2)) puts("Yes");
else puts("No");
}
}