前言
很模板的一道题
传送门 :
思路
将字符串转换为 p p p进制数,同时记录他们之间的 次方
然后需要查询一段字符串的时候直接
h
[
r
]
−
h
[
l
−
1
]
∗
p
[
r
−
l
+
1
]
;
h[r] - h[l-1]*p[r-l+1];
h[r]−h[l−1]∗p[r−l+1]; 即可
CODE
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned
#define ll long long
#define endl '\n'
const int N = 1e5+10 , P= 131;
char str[N];
ull h[N],p[N];
ull get(int l,int r)
{
return h[r] - h[l-1]*p[r-l+1];
}
void solve()
{
int n,m;cin>>n>>m;
cin>>(str+1);
p[0] = 1;
for(int i=1;i<=n;i++)
{
h[i] = h[i-1]*P + str[i];
p[i] = p[i-1]*P;
}
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;
}
}
signed main()
//int main()
{
ios::sync_with_stdio(false);
solve();
return 0;
}