引入

给定两个字符串 s 和 t，如何快速判断 s 的某个子串是否等于 t？

暴力比较每个字符的时间复杂度为 O(|t|)，在需要多次比较时开销较大。

字符串哈希的思想是：将字符串映射为一个整数（称为哈希值），通过比较哈希值来代替逐字符比较，从而实现 O(1) 判断两个字符串是否相等。

当然，不同字符串的哈希值可能相同（称为哈希冲突），所以哈希判断是概率正确的。但通过合理选取参数，冲突的概率可以做到极低。

多项式哈希

定义

对于一个长度为 n 的字符串 s = s1s2⋯sn，定义其哈希值为

其中 b 为基数（base），M 为模数。

本质上是将字符串看作一个 b 进制数。

展开即 H(s) = s1 × bn − 1 + s2 × bn − 2 + ⋯ + sn − 1 × b + sn (mod  M)

参数选取

  • b 通常取一个大于字符集大小的质数，如 131 或 13331。
  • M 通常取一个大质数，如 109 + 7 或 109 + 9。

也有不少人直接用 unsigned long long 自然溢出，等价于 M = 264，但这样容易被卡。

关于自然溢出被卡

存在构造方法可以针对 M = 264 生成大量冲突。竞赛中如果出题人有意卡自然溢出，就会出问题。

安全的做法是取一个大质数作为模数，或者使用双模数哈希。

前缀哈希与子串哈希

预处理前缀哈希值 hi = H(s1s2⋯si)，即 hi = hi − 1 × b + si (mod  M) 初始条件 h0 = 0。

同时预处理 b 的幂次 pi = bi mod  M。

那么子串 slsl + 1⋯sr 的哈希值可以 O(1) 求出： H(sl⋯sr) = hr − hl − 1 × pr − l + 1 (mod  M)

推导

hr = s1 × br − 1 + ⋯ + sl − 1 × br − l + 1 + sl × br − l + ⋯ + sr hl − 1 × pr − l + 1 = (s1 × bl − 2 + ⋯ + sl − 1) × br − l + 1 = s1 × br − 1 + ⋯ + sl − 1 × br − l + 1 两式相减即得 hr − hl − 1 × pr − l + 1 = sl × br − l + ⋯ + sr = H(sl⋯sr)

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using lint = long long;
const lint MOD = 1e9 + 7, BASE = 131;
const int N = 1e6 + 10;

char s[N];
lint h[N], pw[N];

void init(int n) {
  pw[0] = 1;
  for (int i = 1; i <= n; ++i)
    pw[i] = pw[i - 1] * BASE % MOD;
  for (int i = 1; i <= n; ++i)
    h[i] = (h[i - 1] * BASE + s[i]) % MOD;
}

lint get(int l, int r) {
  return (h[r] - h[l - 1] * pw[r - l + 1] % MOD + MOD) % MOD;
}

注意取模时要加 MOD 再取模，防止出现负数。

双模数哈希

使用两组不同的 (b, M) 分别计算哈希值，将两个哈希值组成二元组 (H1, H2)。只有当两个哈希值都相等时，才认为字符串相等。

这样冲突概率大约为 ，当 M1, M2 ∼ 109 时，冲突概率约为 10−18，基本可以认为不会冲突。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const lint MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
const lint BASE1 = 131, BASE2 = 13331;

lint h1[N], h2[N], pw1[N], pw2[N];

void init(int n) {
  pw1[0] = pw2[0] = 1;
  for (int i = 1; i <= n; ++i) {
    pw1[i] = pw1[i - 1] * BASE1 % MOD1;
    pw2[i] = pw2[i - 1] * BASE2 % MOD2;
    h1[i] = (h1[i - 1] * BASE1 + s[i]) % MOD1;
    h2[i] = (h2[i - 1] * BASE2 + s[i]) % MOD2;
  }
}

std::pair<lint, lint> get(int l, int r) {
  return {
    (h1[r] - h1[l - 1] * pw1[r - l + 1] % MOD1 + MOD1) % MOD1,
    (h2[r] - h2[l - 1] * pw2[r - l + 1] % MOD2 + MOD2) % MOD2
  };
}

例题

兔子与兔子

例题：洛谷 P3370 【模板】字符串哈希。

题意简述

给定 n 个字符串，求其中不同字符串的个数。

算法分析

对每个字符串计算哈希值，然后去重统计即可。

时间复杂度 O (∑|si|)（不考虑排序/去重的 log ）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using lint = long long;
const lint MOD = 1e9 + 7, BASE = 131;

lint getHash(const std::string &s) {
  lint res = 0;
  for (char c : s)
    res = (res * BASE + c) % MOD;
  return res;
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  int n;
  std::cin >> n;
  std::set<lint> st;
  for (int i = 0; i < n; ++i) {
    std::string s;
    std::cin >> s;
    st.insert(getHash(s));
  }
  std::cout << st.size() << '\n';
  return 0;
}

二进制哈希与子串匹配

例题：洛谷 P3501 [POI2010] ANT-Antisymmetry。

晚点写。

哈希判断回文串

给定字符串 s，判断子串 sl⋯sr 是否为回文串。

算法分析

维护正向和反向两个哈希值。设 s′ 为 s 的反转，即 s′i = sn − i + 1。

  • 正向哈希 H(sl⋯sr)
  • 反向哈希 H(s′n − l + 1⋯s′n − r + 1) = H(sr⋯sl)

如果两个哈希值相等，则 sl⋯sr 是回文串。

结合二分可以在 O(log n) 的时间内求出以某个位置为中心的最长回文子串长度。当然，如果要求所有位置的最长回文半径，Manacher 算法更优（O(n)）。

哈希的局限性

  • 哈希是概率正确的，存在被卡的可能。在对正确性要求极高的场合（如交互题），需要谨慎使用。
  • 哈希只能判断相等与否，不能比较字典序大小。但可以配合二分来比较字典序：二分最长公共前缀长度，然后比较下一个字符。
  • 涉及修改时，朴素哈希不方便维护。可以搭配线段树维护区间哈希值，支持单点修改和区间查询。