【字符串哈希】CH_1401 兔子与兔子

本文主要是介绍【字符串哈希】CH_1401 兔子与兔子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一个字符串，判断其中的两个区间是否相等。

思路

设$f[i]$为字符串$s[1\sim i]$的$base$进制哈希值，则：
$$f[i]=f[i-1]\ast base+s[i]$$
取出$s[l\sim r]$的哈希值为：
$$f[r]-f[l-1]\ast bas{e}^{r-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");elseprintf("No\n");}
}

这篇关于【字符串哈希】CH_1401 兔子与兔子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---