字符串哈希

字符串哈希又称，字符串的前缀哈希法

个人感觉比kmp算法适用性更强

字符串哈希-acwing 841

又称，字符串的前缀哈希法

个人感觉比kmp算法适用性更强

算法思路

将一个字符串，转化为$p$进制的数，然后除留取余（散列函数）进行哈希映射。

例如上图中例①，将字符串$ABCD$转化为一个四进制的数，然后再$\bmod Q$，最终将字符串映射到$0\sim Q-1$。

注意事项：

1. 不能将字符映射成0
2. 不考虑冲突的处理。假定不会冲突？？？（可能冲突概率太小）

y总经验之谈：

一般情况下，设定

$p=131$或者$p = 13331$

$Q=2^{64}$

99.99%不会产生冲突

---

利用前缀字符串的哈希值，来求任意子串的哈希值。

已知$h[L-1]$和$h[R]$，如何求$L \sim R$的哈希值？

核心公式：

$h[L\sim R] = h[R] - h[L - 1]\times{p^{R-(L-1)}}$

简单举例：

可以快速判断两个子字符是否相同（根据哈希值是否相同来判断）

---

字符串哈希-acwing 841

问题描述

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

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

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

数据范围

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

完整代码

关于以下代码：

1. 字符串哈希中推荐设定的$Q=2^{64}$，正好是unsigned long long类型变量的范围，因此这里在极大概率不会冲突的前提下，直接使用ULL存储哈希值，如果冲突则溢出。
2. 记住以下操作，要熟练。

#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N]; // 先预处理p^n，保存结果

// 核心公式
// 计算子字符串s[l~r]的哈希值
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    scanf("%d%d", &n, &m);
    scanf("%s", str + 1); // 从下标1开始存储
    // 预处理
    p[0] = 1;
    for (int i = 1; i <= n; i ++ ) {
        h[i] = h[i - 1] * P + str[i]; // 这里直接用每个字符的ascii码值来指代
        p[i] = p[i - 1] * P; 
    }

    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;
}