AcWing 841. 字符串哈希
原题链接
简单
作者:
南川嘉子
,
2024-06-10 22:31:45
,
所有人可见
,
阅读 1
#include<iostream>
using namespace std;
const int N=100010;
const int P=131;
typedef unsigned long long ULL;//int范围是到2^31
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(){
int n,m;
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];
}
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");
}
}
return 0;
}