AcWing 841. 字符串哈希
原题链接
简单
作者:
Coding酥
,
2024-02-13 19:43:40
,
所有人可见
,
阅读 36
#include<iostream>
using namespace std;
typedef unsigned long long ULL; // 限定在2^64范围之内
const int N = 100010, pp = 131;
// p[i]存储pp进制数的位差
// h[i]存储前i个字符串的hash值(将字符串每个字母ASCII值看作是p进制数每位上的数,转化为十进制数即为hash值)
ULL p[N], h[N];
char str[N];
int n, m;
int get(int l, int r){
// 将关于1-l的字符串的p进制数左移与1-r的字符串同步,再相减得到hash差值
return h[r] - h[l - 1] * p[r - l + 1];
}
int main(){
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
cin >> n >> m >> str+1;
// 初始化
p[0] = 1;
for(int i = 1; i <= n; i++){
p[i] = p[i - 1] * pp;
h[i] = h[i - 1] * pp + 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;
}