AcWing 841. 字符串哈希
原题链接
简单
作者:
minux
,
2020-04-24 23:40:40
,
所有人可见
,
阅读 470
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
// 字符串转为哈希表达式
const int N=1e5+5;
const int P=131;
int n, m;
char str[N];
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);
memset(h, 0x00, sizeof h);
memset(p, 0x00, sizeof p);
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;
cin>>l1>>r1>>l2>>r2;
if(get(l1, r1)==get(l2, r2))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}