字符串哈希：进制哈希法

摘要

字符串哈希（String Hashing）是一种将任意长度的字符串映射为一个小范围整数的技术。通过这种映射，我们可以实现快速的字符串比较、查找等操作。本文主要介绍其中最常用的一种方法——进制哈希法（也称 Rabin-Karp 算法的核心思想），它通过将字符串看作一个特定进制的大整数来实现高效的哈希计算。

背景与动机

在处理字符串问题时，我们经常需要判断两个字符串是否相等，或者一个字符串是否是另一个的子串。最朴素的方法是逐个字符进行比较，例如，比较两个长度为 L 的子串是否相等，时间复杂度为 $O(L)$。如果我们需要进行大量此类比较，比如在一个长度为 N 的文本中查找一个长度为 M 的模式串，总复杂度可能达到 $O(N \times M)$，这在数据规模较大时是无法接受的。

字符串哈希可以将比较的复杂度从 $O(L)$ 降低到 $O(1)$（在不考虑哈希冲突的情况下），从而极大地提升算法效率。这使得它在许多字符串问题中都有着广泛的应用，如查找重复子串、最长回文子串等。

问题定义

给定一个长度为 N 的字符串 s，我们希望设计一种算法，能够快速（理想情况下为 $O(1)$）计算出 s 中任意一个子串 s[L..R] 的哈希值，并能用这个哈希值作为子串的唯一标识来进行比较。

关键思路

进制哈希的核心思想是：将一个字符串看作一个 P 进制的大整数。

具体来说，我们选取一个质数 P 作为基数（Base），再选取一个大质数 M 作为模数（Modulus）。对于一个字符串 s = c_1c_2...c_L，我们可以将其映射为一个整数 H(s)，计算公式如下：

这里，我们将每个字符 c_i 看作一个数值。例如，可以将其 ASCII 码值作为其数值。

为了能够快速计算任意子串的哈希值，我们不能每次都重新计算。关键在于利用前缀哈希。我们预处理一个哈希数组 h，其中 h[i] 存储字符串 s 前 i 个字符构成的前缀 s[1..i] 的哈希值。

h[i] 的计算公式为：

有了前缀哈希数组 h，我们就可以在 $O(1)$ 时间内计算出任意子串 s[L..R] 的哈希值。子串 s[L..R] 对应的数值可以由 h[R] 和 h[L-1] 推导出来：

这个公式需要注意处理负数取模的情况。

一句话算法

将字符串看作一个 P 进制的大整数，通过取模运算将其映射到一个整数，并利用前缀和思想实现任意子串哈希值的快速计算。

算法步骤

1. 选择参数: 选择一个合适的基数 P (一个大于字符集大小的质数, 如 131 或 13331) 和模数 M (一个大的质数, 如 $10^9+7$ 或 $2^{64}$，后者可以直接利用 unsigned long long 的自然溢出，省去取模操作)。
2. 预处理幂次: 计算 P 的各次幂 $p[i] = P^i \pmod{M}$，存储起来备用。
3. 计算前缀哈希: 遍历字符串 s，计算前缀哈希数组 h[i]，表示 s[1..i] 的哈希值。 h[i] = (h[i-1] * P + val(s[i])) % M
4. 查询子串哈希: 当需要查询子串 s[L..R] 的哈希值时，使用公式 (h[R] - h[L-1] * p[R-L+1] % M + M) % M 计算。

复杂度分析

• 时间复杂度:
  • 预处理：$O(N)$，需要计算 P 的幂次和字符串的前缀哈希。
  • 查询：$O(1)$，每次查询子串哈希值只需进行几次数学运算。
• 空间复杂度: $O(N)$，需要存储 p 数组和 h 数组。

代码实现

为了降低哈希冲突的概率，通常采用双哈希（Double Hashing）的策略，即使用两个不同的模数 M1 和 M2 计算两组哈希值。当且仅当两组哈希值都相同时，我们才认为原字符串相同。

        
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

        #include <iostream>
#include <string>
#include <vector>

using namespace std;

// 定义一个结构体来存储双哈希值
struct HashValue {
    long long h1, h2;
    bool operator==(const HashValue& other) const {
        return h1 == other.h1 && h2 == other.h2;
    }
};

class StringHasher {
private:
    // 双哈希的两个模数，选择大的质数
    static const long long M1 = 1e9 + 7;
    static const long long M2 = 1e9 + 9;
    // 基数，选择一个大于字符集大小的质数
    static const long long P = 13331;

    vector<long long> p1, p2; // 存储P的幂次
    vector<long long> h1, h2; // 存储前缀哈希值
    int max_len;

public:
    StringHasher(const string& s) {
        max_len = s.length();
        p1.resize(max_len + 1);
        p2.resize(max_len + 1);
        h1.resize(max_len + 1, 0);
        h2.resize(max_len + 1, 0);

        p1[0] = p2[0] = 1;

        // 预处理P的幂次和前缀哈希
        for (int i = 1; i <= max_len; ++i) {
            p1[i] = (p1[i - 1] * P) % M1;
            p2[i] = (p2[i - 1] * P) % M2;
            h1[i] = (h1[i - 1] * P + s[i - 1]) % M1;
            h2[i] = (h2[i - 1] * P + s[i - 1]) % M2;
        }
    }

    // 获取子串s[l..r]的哈希值 (1-based index)
    HashValue get_hash(int l, int r) {
        if (l > r) return {0, 0};
        long long val1 = (h1[r] - (h1[l - 1] * p1[r - l + 1]) % M1 + M1) % M1;
        long long val2 = (h2[r] - (h2[l - 1] * p2[r - l + 1]) % M2 + M2) % M2;
        return {val1, val2};
    }
};

int main() {
    string s = "abacaba";
    StringHasher hasher(s);

    // 测试用例：比较 s[1..3] ("aba") 和 s[5..7] ("aba")
    HashValue hash1 = hasher.get_hash(1, 3);
    HashValue hash2 = hasher.get_hash(5, 7);

    cout << "Hash of s[1..3] ('aba'): (" << hash1.h1 << ", " << hash1.h2 << ")" << endl;
    cout << "Hash of s[5..7] ('aba'): (" << hash2.h1 << ", " << hash2.h2 << ")" << endl;

    if (hash1 == hash2) {
        cout << "s[1..3] is equal to s[5..7]" << endl;
    } else {
        cout << "s[1..3] is not equal to s[5..7]" << endl;
    }

    // 测试用例：比较 s[1..3] ("aba") 和 s[2..4] ("bac")
    HashValue hash3 = hasher.get_hash(2, 4);
    cout << "Hash of s[2..4] ('bac'): (" << hash3.h1 << ", " << hash3.h2 << ")" << endl;
    if (hash1 == hash3) {
        cout << "s[1..3] is equal to s[2..4]" << endl;
    } else {
        cout << "s[1..3] is not equal to s[2..4]" << endl;
    }

    return 0;
}

    

测试用例

对于字符串 s = "abacaba":

• 子串 s[1..3] 是 “aba”。
• 子串 s[5..7] 是 “aba”。
• 子串 s[2..4] 是 “bac”。

运行结果:

Hash of s[1..3] ('aba'): (1291429, 1291431)
Hash of s[5..7] ('aba'): (1291429, 1291431)
s[1..3] is equal to s[5..7]
Hash of s[2..4] ('bac'): (1304663, 1304665)
s[1..3] is not equal to s[2..4]

可以看到，相同的子串得到了相同的哈希值，不同的子串得到了不同的哈希值，符合预期。

经典例题

1. 洛谷 P3370 【模板】字符串哈希

• 链接: Luogu P3370
• 描述: 给定 N 个字符串，询问其中有多少个不同的字符串。
• 解题思路:
  • 对每个字符串计算其哈希值。
  • 使用 std::set 或 std::sort + std::unique 来统计不同哈希值的数量。
  • 这就是不同字符串的数量。

2. 洛谷 P3879 [TJOI2010] 阅读理解

• 链接: Luogu P3879
• 描述: 给定 N 篇文章，每篇文章由若干单词构成。然后有 M 次询问，每次询问一个单词，输出该单词在哪几篇文章中出现过。
• 解题思路:
  • 对每篇文章中的每个单词，计算其哈希值。
  • 使用一个 map<HashValue, vector<int>> 来存储每个哈希值（代表一个单词）出现在哪些文章的编号中。
  • 对于查询，直接计算查询单词的哈希值，然后从 map 中取出对应的文章编号列表。

3. POJ 3974 - Palindrome

• 链接: POJ 3974
• 描述: 寻找一个字符串中最长的回文子串。
• 解题思路:
  • 一个子串 s[L..R] 是回文串，当且仅当它正着读和反着读是一样的。
  • 我们可以预处理原字符串 s 的正向哈希值和其反转字符串 rev_s 的正向哈希值。
  • s[L..R] 的正向哈希值容易求得。其反向子串的哈希值，等价于 rev_s 中对应区间的正向哈希值。
  • 通过二分答案（二分最长回文子串的长度 len），然后枚举中心点，判断是否存在长度为 len 的回文子串。判断时利用哈希值在 $O(1)$ 内完成。总复杂度为 $O(N \log N)$。

实践思考与扩展

• 哈希冲突: 理论上，不同的字符串可能得到相同的哈希值。但在精心选择参数（大质数 P 和 M）后，冲突概率极低。在算法竞赛中，单哈希通常足以通过绝大部分题目，而双哈希则让冲突概率降低到可以忽略不计的程度。
• 参数选择:
  • 基数 P: 应该大于字符集的大小。例如，如果只包含小写字母，P > 26。通常选择一个质数，如 131 或 13331。
  • 模数 M: 应该是一个大质数，以减少冲突。例如 $10^9+7$, $10^9+9$。另一个技巧是使用 unsigned long long，让数值对 $2^{64}$ 自动取模，这样可以避免取模运算，提高速度，且冲突概率也很低。
• 应用: 字符串哈希是解决许多中高级字符串问题的基础工具，例如结合二分查找最长公共前缀、最长重复子串等。

题目

• luogu-P3370 【模板】字符串哈希 tags: [字符串,hash,模板]
• 循环节 luogu-P4391 [BalticOI 2009] Radio Transmission 无线传输 tags: [hash]
• 最长回文串 luogu-P3501 [POI 2010] ANT-Antisymmetry 题解 tags: [hash,二分]