字符串哈希

介绍

利用哈希的思想，实现快速判断两个字符串是否相同。

例题

题目描述

给定一个长度为 $n$ 的字符串，再给定 $m$ 个询问，每个询问包含四个整数 $l_1,r_1,l_2,r_2$，请你判断 $l_1, r_1$和 $l_2, r_2$ 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 $n$ 和 $m$，表示字符串长度和询问次数。

第二行包含一个长度为 $n$ 的字符串，字符串中只包含大小写英文字母和数字。

接下来 $m$ 行，每行包含四个整数 $l_1,r_1,l_2,r_2$，表示一次询问所涉及的两个区间。

注意，字符串的位置从 $1$ 开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

输入样例

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例

Yes
No
Yes

题解

根据哈希的思想，我们选择一个类似进制转换的哈希函数。

如 aabb 这个字符串，其映射值为：
$$
(a * P^0+a * P^1+b * P^3+b * P^4)\bmod Q
$$
本题里，我们将其从前往后按照前缀的方式存到 h[] 中，那么有：

h[1] = 'a' 的映射值
h[2] = 'aa' 的映射值
h[3] = 'aab' 的映射值
h[4] = 'aabb' 的映射值

而映射时有几个注意点：

• $P$ 通常取 $133$ 或 $13331$ ，经验证明这样很少发生碰撞。
• 字母不能映射成 $0$ 否则会发生冲突 ：如果a -> 0 那么 aa -> 0

我们要想知道 $[l_1, r_1]$ 和 $[l_2, r_2]$ 是否相同，那么只要判断二者的哈希值是否相等。那么如何判断二者是否相等呢？

问题就转化为：已知 h[l1], h[r1] 的值，如何求得 $[l_1, r_1]$ 这一段的哈希值？

答案是：将 h[l1] 左移 $r-l+1$ 位，它与 h[r1] 的差值就是我们想要求的。如 aa 的哈希值右移两位就是 aa00 ，然后用 aabb 的哈希值减去 aa00 ，就得到 bb 的哈希值。代码如下：

h[r] - h [l - 1] * p[r - l + 1]

代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL;
const int N = 100010, P = 131;
int n, m;
ULL h[N], p[N];
char str[N];

ULL get(int l, int r) {
    return h[r] - h [l - 1] * p[r - l + 1];
}


int main() {
    scanf("%d%d%s", &n, &m,  str + 1);  // 从 str[1]开始存

    p[0] = 1;
    // 预处理h[N]和p[N]
    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;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    
    return 0;
}