我的算法书 - 字符串哈希：进制哈希法

一句话算法

把字符串看成一个 $P$ 进制大整数，预处理前缀哈希后，用“整段减去前缀”在 $O(1)$ 得到任意子串的哈希值。

问题模型

给定一个字符串 $s$ ，需要多次判断两个子串是否相同：

s[l1..r1] 是否等于 s[l2..r2]

朴素比较需要逐字符扫描，单次最坏 $O(\text{len})$ 。当查询很多时，总复杂度会很高。

字符串哈希把每个子串映射成整数。比较两个子串时，先比较长度，再比较哈希值。哈希相等时通常认为字符串相等。

“哈希冲突”

字符串哈希有极小概率发生冲突。竞赛中常用 unsigned long long 自然溢出、双哈希或大质数取模降低风险。

核心直觉

十进制数可以用前缀相减截取一段数字：

12345 中截出 345 = 12345 - 12 * 1000

字符串哈希也是同一个模型。把字符当成数字，把字符串当成 $P$ 进制数：

H(s_1s_2\cdots s_n) = s_1P^{n-1}+s_2P^{n-2}+\cdots+s_n

如果已经知道前缀 s[1..r] 的哈希值和前缀 s[1..l-1] 的哈希值，就可以把前面的部分减掉，留下 s[l..r]。

算法步骤

选择一个进制基数 BASE，常用 131、13331。
预处理：
- power[i] = BASE^i；
- prefix[i] = prefix[i-1] * BASE + s[i]。
查询子串 [l,r]：

hash(l,r) = prefix[r] - prefix[l-1] * power[r-l+1]

判断两个子串是否相等：
- 长度不同，直接不同；
- 长度相同，比较哈希值。

算法证明

核心不变量：prefix[i] 表示前缀 s[1..i] 作为 $P$ 进制数时的哈希值。

预处理时：

prefix[i]=prefix[i-1]\cdot P+s_i

这等价于把旧前缀整体左移一位，再放入新字符，所以不变量成立。

对子串 [l,r]，设 len = r-l+1。前缀 s[1..r] 可以拆成两段：

s[1..r] = s[1..l-1] + s[l..r]

算式推导：

\begin{aligned} prefix[r] &= prefix[l-1]\cdot P^{len}+H(s[l..r]) \\ H(s[l..r]) &= prefix[r]-prefix[l-1]\cdot P^{len} \end{aligned}

所以查询公式正确。

复杂度分析

设字符串长度为 $n$ ，查询次数为 $q$ 。

预处理时间复杂度： $O(n)$ 。
单次查询时间复杂度： $O(1)$ 。
总时间复杂度： $O(n+q)$ 。
空间复杂度： $O(n)$ 。

代码实现

模板输入格式：

s
q
l1 r1 l2 r2
...

每个询问判断两个 1-based 子串是否相同，输出 Yes 或 No。

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

        #include <bits/stdc++.h>
using namespace std;

struct StringHash {
    using ull = unsigned long long;

    static constexpr ull BASE = 131;
    vector<ull> prefix;
    vector<ull> power;

    StringHash(const string &s) {
        int n = (int)s.size();
        prefix.assign(n + 1, 0);
        power.assign(n + 1, 1);

        for (int i = 1; i <= n; i++) {
            power[i] = power[i - 1] * BASE;
            prefix[i] = prefix[i - 1] * BASE + (unsigned char)s[i - 1];
        }
    }

    // 返回 1-based 子串 s[l..r] 的哈希值。
    ull get(int l, int r) const {
        if (l > r) return 0;
        return prefix[r] - prefix[l - 1] * power[r - l + 1];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    StringHash hs(s);

    int q;
    cin >> q;
    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (r1 - l1 != r2 - l2) {
            cout << "No\n";
            continue;
        }
        cout << (hs.get(l1, r1) == hs.get(l2, r2) ? "Yes" : "No") << '\n';
    }

    return 0;
}

测试用例

输入：

abacaba
3
1 3 5 7
1 3 2 4
2 2 6 6

输出：

Yes
No
Yes

解释：

s[1..3] = "aba"，s[5..7] = "aba"。
s[1..3] = "aba"，s[2..4] = "bac"。
s[2..2] = "b"，s[6..6] = "b"。

应用分类详解

字符串哈希的本质是“把一段字符串压成可快速比较的指纹”。看到大量子串比较、重复判断、模式匹配时，可以考虑它。

一、静态子串相等判断

典型模式： 一个字符串固定，多次询问两个子串是否相同。

识别信号： 出现“多次比较子串”“判断两个区间字符串是否一样”。

核心建模： 预处理前缀哈希，每个子串用 hash(l,r) 表示。

应用场景	经典题目	核心思路
子串相等查询	本页模型	长度相同且哈希相同
最长公共前缀	后缀比较类问题	二分长度，每次用哈希判等

二、去重与集合统计

典型模式： 给出很多字符串或很多子串，统计不同个数。

识别信号： 出现“不同字符串数量”“去重”“重复子串”。

核心建模： 把每个字符串或子串的哈希值放入 set，再统计集合大小。

应用场景	经典题目	核心思路
字符串去重	luogu-P3370	每个字符串求哈希后排序去重
重复子串判断	最长重复子串	二分长度，检查是否有重复哈希

三、模式匹配

典型模式： 在文本串中查找模式串是否出现。

识别信号： 出现“模式串”“文本串”“匹配位置”。

核心建模： 先求模式串哈希，再枚举文本中的等长窗口比较哈希。

四、回文与循环结构判断

典型模式： 判断一个子串是否回文，或判断字符串是否存在周期。

识别信号： 出现“正反相同”“循环节”“周期”。

核心建模： 回文可比较正向哈希与反向哈希；循环节可比较相邻重复块哈希。

经典例题

1. luogu-P3370

字符串哈希模板题。对每个字符串求哈希，排序去重后得到不同字符串数量。

2. luogu-P4391

循环节问题。可以用 KMP，也可以用哈希辅助判断重复块是否一致。

3. luogu-P3501

回文相关问题。正反哈希可以快速判断某段是否回文，适合和二分或枚举中心结合。

参考

Rabin-Karp 字符串匹配思想。