44 lines
1.2 KiB
C++
44 lines
1.2 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
//省代码写法
|
||
typedef unsigned long long ULL;
|
||
|
||
const int N = 1000010, P = 131; //经验 或者 13331，取这两值的冲突概率低
|
||
|
||
int m;
|
||
char str[N]; //字符串
|
||
ULL h[N], p[N]; //h表示某一个前缀的HASH值,h[k]表示的是前k个字母的HASH值,p[k]存储P^k mode 2^64
|
||
|
||
//计算部分字符串的HASH值
|
||
ULL get(int l, int r) {
|
||
return h[r] - h[l - 1] * p[r - l + 1];
|
||
}
|
||
|
||
//模板裸题啊！
|
||
|
||
int main() {
|
||
//输入+输出重定向
|
||
freopen("../AcWing/N6/138.txt", "r", stdin);
|
||
//计算字符串前缀的HASH值，就是预处理
|
||
scanf("%s%d", str + 1, &m);
|
||
//预处理
|
||
p[0] = 1;
|
||
int n = strlen(str + 1);//因为我们把字符串放的时候放弃了索引0，所以这里strlen就也需要躲开0.
|
||
for (int i = 1; i <= n; i++) {
|
||
p[i] = p[i - 1] * P;
|
||
h[i] = h[i - 1] * P + str[i];
|
||
}
|
||
//然后根据公式计算两个区间的字符串HASH值是不是相同
|
||
while (m--) {
|
||
int l1, r1, l2, r2;
|
||
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
|
||
if (get(l1, r1) == get(l2, r2))puts("Yes");
|
||
else puts("No");
|
||
}
|
||
|
||
//关闭文件
|
||
fclose(stdin);
|
||
return 0;
|
||
} |