题意
给出一个字符串，判断其中的两个区间是否相等。
思路
设f[i]f[i]f[i]为字符串s[1∼i]s[1\\sim i]s[1∼i]的basebasebase进制哈希值，则：
f[i]=...
题意
给出一个字符串，判断其中的两个区间是否相等。
思路
设f[i]为字符串s[1∼i]的base进制哈希值，则：
f[i]=f[i−1]∗base+s[i]
取出s[l∼r]的哈希值为：
f[r]−f[l−1]∗baser−l+1
相当于我们把一个l−1位的数在后面补满0，然后用f[r]减去，得到这一段的结果。
代码
#include<cstdio>
#include<cstring>
char s[1000001];
unsigned long long f[1000001], p[1000001];
int main() {
scanf(\"%s\", s + 1);
int m, n = strlen(s + 1);
p[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = f[i - 1] * 131 + s[i] - \'a\' + 1;
p[i] = p[i - 1] * 131;
}
scanf(\"%d\", &m);
int l1, r1, l2, r2;
for (; m; m--) {
scanf(\"%d %d %d %d\", &l1, &r1, &l2, &r2);
if (f[r1] - f[l1 - 1] * p[r1 - l1 + 1] == f[r2] - f[l2 - 1] * p[r2 - l2 + 1])
printf(\"Yes\\n\");
else
printf(\"No\\n\");
}
}
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：C#两行代码实现三维地球 下一篇：（翻译）第五回 开始使用JavaFX2.0
