AcWing 841. 字符串哈希
原题链接
简单
作者:
szywdwd
,
2021-05-25 13:35:44
,
所有人可见
,
阅读 180
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
// 当P进制取131、13331,模数Q取2的64次方时,出现冲突几率将近万分之一
const int N = 100010, P = 131;// 字符串前缀转化成P进制数
char str[N];
ULL h[N], p[N];// 溢出自动取2的64次方的模
int n, m;
ULL get(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
cin >> n >> m >> str + 1;// str[0] = 0
// 初始化h、p数组,p[i]表示P的i次方
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;
cout << (get(l1, r1) == get(l2, r2) ? "Yes" : "No") << endl;
}
return 0;
}