AcWing 841. 字符串哈希
原题链接
简单
作者:
piaofan
,
2021-02-06 19:15:53
,
所有人可见
,
阅读 253
#include<iostream>
using namespace std;
const int N = 100005, P = 131;
typedef unsigned long long ULL;
char s[N];
ULL h[N], p[N];
ULL geth (int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
int main (void) {
int n, m;
scanf("%d%d", &n, &m);
scanf("%s", s + 1);
p[0] = 1;
for (int i = 1; i <= n; i++) {
h[i] = h[i - 1] * P + s[i];
p[i] = p[i - 1] * P;
}
while (m--) {
int l1, l2, r1, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (geth(l1, r1) == geth(l2, r2)) printf("Yes\n");
else printf("No\n");
}
return 0;
}