AcWing 841. 字符串哈希
原题链接
简单
作者:
cyeoopp
,
2025-04-09 20:15:33
· 甘肃
,
所有人可见
,
阅读 2
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const int N=1e6+10;
const int P=1331;
string s;
LL h[N],p[N];
int nn,mm;
LL get_(int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
string b="#";
cin>>nn>>mm;
cin>>s;
s=b+s;
nn=s.size()-1;
p[0]=1;
for(int i=1;i<=nn;i++)
{
p[i]=p[i-1]*P;
h[i]=h[i-1]*P+s[i];
}
while(mm--)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
if(get_(a,b)==get_(c,d))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}