AcWing 841. 字符串哈希
原题链接
简单
作者:
大笔筒
,
2022-02-20 15:48:13
,
所有人可见
,
阅读 128
#include<iostream>
using namespace std;
typedef unsigned long long ULL;
const int N=1e5+10,P=131;
char str[N];
ULL h[N],p[N];
int n,m;
bool check(int l1,int r1,int l2,int r2)
{
if(h[r1]-h[l1-1]*p[r1-l1+1]==h[r2]-h[l2-1]*p[r2-l2+1])
return true;
return false;
}
int main()
{
cin>>n>>m;
cin>>(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;cin>>l1>>r1>>l2>>r2;
if(check(l1,r1,l2,r2)==true) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}