AcWing 841. 字符串哈希
原题链接
简单
作者:
术
,
2021-01-19 09:24:26
,
所有人可见
,
阅读 243
#include <iostream>
using namespace std;
string str;
int n,m;
const int P=13331;
const int N=100003;
const int Q=2e64-1;
int h[N],p[N];//或者用unsign long long 不用取模了
int get_snum(int a,int b){
return h[b]-h[a-1]*p[b-a+1];
}
int main()
{
cin>>n>>m;
cin>>str;
p[0]=1;
for(int i=1;i<=n;i++){
p[i]=(p[i-1]*P)%Q;//左移i位
h[i]=(h[i-1]*P+str[i-1]+Q)%Q;
}
while(m--){
int a,b,c,d;
cin>>a>>b>>c>>d;
//cout<<get_snum(a,b)<<" "<<get_snum(c,d)<<endl;
if(get_snum(a,b)==get_snum(c,d))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
//cout << "Hello world!" << endl;
return 0;
}