【字符串哈希】字符串哈希

题目

841. 字符串哈希

---

给定一个长度为 $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。

每个结果占一行。

数据范围

$1 \le n, m \le 10^5$

输入样例：

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

输出样例：

Yes
No
Yes

解题

方法一：字符串前缀哈希法

思路

使用字符串前缀哈希法求字符串哈希时，一般会先预处理出该字符串所有前缀的哈希，例如：str = "ABCDE"，那么：

h[0] = 0;
h[1] = hash("A");
h[2] = hash("AB");
h[3] = hash("ABC");
h[4] = hash("ABCD");
h[5] = hash("ABCDE");
// h[k] 表示字符串中前k个字母的哈希值

字符串哈希函数的设计：把字符串看成是一个 $P$ 进制的数，然后把这个数转为十进制，转换之后得到的十进制数可能会很大，所以最后会把它对一个数 $Q$ 取模，这样就可以把任意一个字符串映射为 $[0, Q-1]$ 之间的一个哈希值，例如 str = "ABCD" 那么：

$$\begin{aligned} hash(str) &= \text{"ABCD"}_{(P)} \mod Q_{(10)} \\ &= (\text{'A'} \times P^3 + \text{'B'} \times P^2 + \text{'C'} \times P^1 + \text{'D'} \times P^0)_{(10)} \mod Q_{(10)} \end{aligned}$$

注意：

• 一般情况下不能把某个字符映射成 $0$。
• 不考虑哈希冲突的情况。
• 经验来说，一般 $P$ 取 $131$ 或 $13331$，$Q$ 取 $2^{64}$（C++ 中用 unsigned long long Java 中用 long 来存储哈希值就可以省去对 $Q$ 取模这一步骤（自然溢出））。

故，迭代求前缀的哈希值：$h[i] = h[i - 1] \times P + str[i]$。

这样求字符串哈希的方式有一个好处，那就是可以利用求得的前缀哈希数组计算出该字符串中任意一个子串的哈希值：

如上图，在前缀哈希数组 $h$ 中 $h[R]$ 与 $h[L - 1]$ 是低位对齐的，而要求出 $hash(R-L)$ 就需要先让 $h[L-1]$ 的高位与 $h[R]$ 的高位先对齐再相减，就有了如下的公式：

$$hash(L...R) = h[R] - h[L - 1] \times P^{R - L + 1}$$

有了这个公式，给定一个字符串，就可以快速的判断其中的任意两个子串是否相同。

（公式中会用到 $P$ 的 $[0, n)$ 次方，可以在维护前缀哈希数组 h 时预处理为数组 p，p[i] 表示 $P^i$）

代码

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e5 + 10, P = 131;
ULL h[N], p[N];
char s[N];
int n, m;

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

int main() {
    scanf("%d%d\n%s\n", &n, &m, s + 1);
    p[0] = 1L;
    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, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        puts(sub_hash(l1, r1) == sub_hash(l2, r2) ? "Yes" : "No");
    }
    
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static final int P = 131;
    static long[] h, p;
    
    static long subHash(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(BR);
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        String str = BR.readLine();
        h = new long[n + 1];
        p = new long[n + 1];
        p[0] = 1;
        for (int i = 1; i <= n; ++i) {
            h[i] = h[i - 1] * P + str.charAt(i - 1);
            p[i] = p[i - 1] * P;
        }
        while (m-- > 0) {
            in.nextToken();
            int l1 = (int) in.nval;
            in.nextToken();
            int r1 = (int) in.nval;
            in.nextToken();
            int l2 = (int) in.nval;
            in.nextToken();
            int r2 = (int) in.nval;
            System.out.println(subHash(l1, r1) == subHash(l2, r2) ? "Yes" : "No");
        }
    }
}