9-字符串哈希--KMP劲敌

字符串哈希

字符串哈希可以把一个字符串映射成一个整数。预处理出所有前缀的哈希值后，就能在 $O(1)$ 时间内求出任意子串的哈希值，从而快速判断两个子串是否相同。

它和 KMP 都能解决字符串匹配问题，但擅长的场景不同：

KMP 适合在线性时间内寻找一个固定模式串在文本中的所有出现位置；
字符串哈希适合预处理一个字符串后，反复比较任意两个子串；
KMP 是确定性算法，不存在误判；
字符串哈希可能发生碰撞，比较结果具有概率性。

在需要大量子串比较、回文判断或重复子串查询时，字符串哈希往往比反复运行 KMP 更灵活，因此可以称为 KMP 劲敌。

把字符串看成 $P$ 进制数

设字符串采用 1-based 下标，字符序列为：

s_1,s_2,\ldots,s_n.

选择一个进制 $P$ ，把每个字符的编码作为一位数字。字符串前缀 $s[1..i]$ 的哈希值定义为：

H(i) =s_1P^{i-1}+s_2P^{i-2}+\cdots+s_{i-1}P+s_i.

例如，把 A、B、C 分别简化为数字 $1$ 、 $2$ 、 $3$ ，并令 $P=10$ ，那么字符串 ABC 的哈希值就是：

1\times 10^2+2\times 10+3=123.

代码中不需要真的展开这个多项式。根据定义，可以递推计算：

H(i)=H(i-1)\times P+s_i.

对应代码为：

h[i] = h[i - 1] * P + str[i];

这里直接使用字符的数值编码，不需要手动把字母转换成 1、2、3。

前缀哈希预处理

除了前缀哈希数组 h，还需要预处理 $P$ 的各次幂：

p[0] = 1;
 
for (int i = 1; i <= n; i++) {
  p[i] = p[i - 1] * P;
  h[i] = h[i - 1] * P + str[i];
}

其中：

h[i] 表示前缀 str[1..i] 的哈希值；
p[i] 表示 $P^i$ ；
h[0] = 0，表示空前缀的哈希值；
p[0] = 1，表示 $P^0=1$ 。

h 和 p 是全局数组，因此会被自动初始化为 0。

求任意子串的哈希值

要计算子串 str[l..r] 的哈希值，可以先观察前缀 str[1..r]：

H(r) =H(l-1)\times P^{r-l+1} +\operatorname{hash}(l,r).

前缀 str[1..l-1] 在 H(r) 中整体向高位移动了 $r-l+1$ 位。因此，把它的哈希值乘上 $P^{r-l+1}$ 后从 H(r) 中减去，就得到子串哈希：

\operatorname{hash}(l,r) =H(r)-H(l-1)\times P^{r-l+1}.

对应代码为：

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

为什么不同位置的相同子串可以直接比较

get(l, r) 会移除子串左侧前缀的贡献，得到一个只与子串内容和长度有关的 $P$ 进制表示。

例如，字符串中的两个 abc 即使起点不同，调用 get 后得到的都是：

aP^2+bP+c.

因此，不需要把两个子串移动到相同位置，也不需要先截取字符串，就可以直接比较它们的哈希值。

使用 `unsigned long long`

完整的 $P$ 进制数会迅速超过普通整数的范围。本模板使用：

using ULL = unsigned long long;

无符号 64 位整数发生溢出时，会按照模 $2^{64}$ 的规则保留结果。因此，所有乘法、加法和减法都可以理解为自动对 $2^{64}$ 取模，不需要手写 % MOD。

因为 h、p 和整个表达式都使用 ULL，即使减法在普通整数意义下得到负数，无符号运算也会自动环绕到对应的模 $2^{64}$ 结果。

本模板选择：

const int P = 131;

131 是字符串哈希中常用的进制。它配合模 $2^{64}$ 可以让常见数据中的碰撞概率很低，但不能从理论上保证完全不发生碰撞。

正确性说明

预处理时，h[0] = 0。假设 h[i - 1] 已经正确表示前缀 str[1..i-1] 的 $P$ 进制哈希值，那么：

h[i]=h[i-1]\times P+str[i]

会把原前缀整体左移一位，再把 str[i] 放到最低位，因此 h[i] 正确表示 str[1..i]。根据数学归纳法，所有前缀哈希值都能被正确计算。

查询 str[l..r] 时，h[l-1] * p[r-l+1] 正好等于左侧前缀 str[1..l-1] 在 h[r] 中的全部贡献。将它从 h[r] 中减去后，只剩下 str[l..r] 的 $P$ 进制哈希值。

如果两个子串完全相同，它们的长度和每一位字符都相同，因此计算出的哈希值一定相同。如果哈希值不同，两个子串也一定不同。

反过来，两个不同的子串仍有极小概率得到相同哈希值，这种情况称为哈希碰撞。因此，本算法的相等判断是概率正确的；需要抵抗刻意构造的数据时，可以使用两组不同的进制或模数进行双哈希。

AcWing 841：字符串哈希

题意

给定一个长度为 $n$ 的字符串和 $m$ 次询问。每次询问给出四个下标：

l1 r1 l2 r2

需要判断子串 str[l1..r1] 与 str[l2..r2] 是否完全相同：

相同则输出 Yes；
不同则输出 No。

字符串只包含大小写英文字母和数字，下标从 1 开始。

解题思路

先在 $O(n)$ 时间内预处理：

所有前缀的哈希值 h[i]；
所有需要的 $P$ 的幂 p[i]。

对于每次询问，分别使用 get 计算两个区间的哈希值，再直接比较。每次询问只进行常数次数组访问和算术运算，时间复杂度为 $O(1)$ 。

完整代码

#include <iostream>
 
using namespace std;
 
using ULL = unsigned long long;
 
const int N = 100010;
const int P = 131;
 
char str[N];
ULL h[N], p[N];
 
ULL get(int l, int r) {
  return h[r] - h[l - 1] * p[r - l + 1];
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int n, m;
  cin >> n >> m >> (str + 1);
 
  p[0] = 1;
 
  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;
    cin >> l1 >> r1 >> l2 >> r2;
 
    if (get(l1, r1) == get(l2, r2)) {
      cout << "Yes" << '\n';
    } else {
      cout << "No" << '\n';
    }
  }
 
  return 0;
}

样例

输入：

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

输出：

Yes
No
Yes

三个询问比较的子串分别为：

aab 与 aab，二者相同；
aab 与 abb，二者不同；
aa 与 aa，二者相同。

复杂度分析

预处理前缀哈希和幂数组的时间复杂度为 $O(n)$ ；
每次询问的时间复杂度为 $O(1)$ ；
$m$ 次询问的总时间复杂度为 $O(n+m)$ ；
h、p 和字符数组的空间复杂度为 $O(n)$ 。

如果直接截取并逐字符比较两个子串，单次询问最坏需要 $O(n)$ 时间，总时间复杂度可能达到 $O(nm)$ 。

常见错误

忘记令 p[0] = 1： $P^0$ 必须为 1，否则整个幂数组都会保持为 0。
区间长度少加 1：闭区间 [l, r] 的长度是 r - l + 1，公式必须使用 p[r - l + 1]。
混用 0-based 和 1-based 下标：本模板从 str + 1 开始读入，查询区间也从 1 开始，左侧前缀应写成 h[l - 1]。
把 p 误认为质数模数：这里的 p[i] 存储 $P^i$ ，P 是字符串哈希的进制，代码没有显式质数模数。
使用有符号整数保存哈希值：有符号整数溢出属于未定义行为，不能用它模拟取模；应使用 unsigned long long。
认为哈希相同就绝对相同：不同字符串可能发生碰撞。普通算法题中单哈希通常足够，安全性要求高或数据可能被针对时应使用双哈希。
直接比较不同定义的哈希值：两个字符串必须使用相同的进制、模数和字符映射方式，哈希值才具有可比性。
逐次查询时重新计算哈希：字符串哈希的优势来自一次预处理、常数时间查询，不能在每次询问中重新遍历子串。

参考资料

AcWing：数据结构（二）—— 单调栈、单调队列、KMP、Trie、并查集、堆、哈希表，作者：yxc（非商业转载请注明出处）。