字符串哈希：给字符串做独一无二的“数字指纹”

想象一下，你有一本厚厚的《新华字典》，你想快速判断第 10 页第 3 行的文字是不是和第 50 页第 8 行的文字一模一样。如果每次都要一个一个字去对比，那得花多少时间呀！字符串哈希就是来解决这个问题的。它像给每个字符串或子串盖上一个“数字指纹”（一个很大的整数），只要比较两个指纹是否相同，就能瞬间知道它们是不是相等（虽然存在极微小的概率出错，但我们可以用双重哈希来几乎完全避免）。这样一来，比较两个子串的时间就从 O(长度) 变成了 O(1)。

为什么要用到哈希？

平时我们比较两个字符串是否相等，只能用循环逐个字符比对。例如判断班里的两个同学是否交了相同的作文，老师只能从头读到尾。如果作文有几十万字，那检查一篇就要很久。而字符串哈希相当于把整篇作文“压缩”成一个数字，以后只需比较数字，轻松又快速。

哈希的原理：把字符串看作一个数字

一个很自然的想法：把字符串当成一个 base 进制 的数，每一位字符对应一个数字（比如 'a' 对应 1，'b' 对应 2，……，'z' 对应 26）。然后对这个数取模（模一个大质数，比如 1e9+7），得到的结果就是该字符串的哈希值。

例如，字符串 "ab"：

• 令 base = 131，字符 'a' 变成数字 1，'b' 变成数字 2。
• 按照公式：hash = (1 × 131¹ + 2 × 131⁰) = 131 + 2 = 133（实际还要取模）。
• 取模后得到 133（因为 133 < 1e9+7）。

这样 "ab" 的指纹就是 133。如果另一个字符串也是 "ab"，它的指纹也是 133，那它们就相等。

如何快速得到任意子串的哈希？

我们不可能每次想要某个子串时都重新从头计算一遍哈希，那样太慢了。所以我们会预处理整个字符串的前缀哈希。
定义 h[i] 表示字符串的前 i 个字符的哈希值（从第一个字符开始）。

例如，字符串 s = "abcd"，base = 131，mod = 1e9+7：

• 空字符串的哈希 h[0] = 0
• "a"：h[1] = (0 × 131 + 1) % mod = 1
• "ab"：h[2] = (h[1] × 131 + 2) % mod = (1×131 + 2) % mod = 133
• "abc"：h[3] = (133 × 131 + 3) % mod = 17426
• "abcd"：h[4] = (17426 × 131 + 4) % mod = 2282810

有了前缀哈希，子串 s[l..r]（下标从 1 开始）的哈希值可以通过公式：

hash(l, r) = (h[r] - h[l-1] * base^(r-l+1) % mod + mod) % mod

这个公式的含义是：用前 r 个字符的哈希减去前 l-1 个字符左移相应位数后的值，就能得到中间那一段的哈希。

比如，想得到子串 "bc"（原字符串第 2 到第 3 个字符）：

• l=2, r=3
• h[3] = 17426，h[1] = 1，base^(r-l+1) = 131² = 17161
• 计算：17426 - 1×17161 = 265，取模后还是 265。
• 如果手动按定义计算 "bc"：'b'=2, 'c'=3，哈希 = 2×131 + 3 = 262+3=265，一致！

所以公式是对的。以后要比较两个子串是否相等，只需比较它们的哈希值。

代码实现细节

下面是一个完整的字符串哈希工具类代码。注意：字符从 'a' 到 'z'，我们把它映射到 1~26（用 1-base 编码，避免哈希值为 0 导致重复）。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef unsigned long long ull;  // 使用unsigned long long可自动溢出取模（等效于取模2^64），比直接取模更快
const int BASE = 131;            // 常用基数，最好是大于字符集大小的质数

// 全局数组，用于存储前缀哈希和base的幂
vector<ull> power;  // power[i] = BASE^i
vector<ull> h;      // h[i] = 前i个字符的哈希值

// 初始化哈希表，传入字符串s
void init_hash(const string& s) {
    int n = s.size();                    // 字符串长度
    power.resize(n + 1, 1);              // 先给power分配空间，power[0] = 1
    for (int i = 1; i <= n; i++)
        power[i] = power[i - 1] * BASE;  // 计算BASE的各个次幂，自然溢出（相当于对2^64取模）

    h.resize(n + 1, 0);                  // h[0] = 0
    for (int i = 0; i < n; i++)
        // 将字符转为数字：'a'->1, 'b'->2, ... , 'z'->26
        h[i + 1] = h[i] * BASE + (s[i] - 'a' + 1);  // 同样自然溢出
}

// 获取子串s[l..r]的哈希值，下标从1开始，包含两端
ull get_hash(int l, int r) {
    // 公式：h[r] - h[l-1] * base^(r-l+1)
    return h[r] - h[l - 1] * power[r - l + 1];
}

int main() {
    string s = "hello world";
    init_hash(s);

    // 注意：我们存储的字符串下标1对应原字符串第0个字符
    // 子串"ello"对应原字符串下标1~4，即我们的l=2, r=5
    ull h1 = get_hash(2, 5);   // "ello"的哈希
    ull h2 = get_hash(7, 10);  // "worl"的哈希
    cout << (h1 == h2 ? "相等" : "不相等") << endl; // 应该输出不相等
    return 0;
}

上面代码使用了 unsigned long long 的自然溢出（自动取模 2^64），省去了手动取模的麻烦，速度更快。但注意：自然溢出可能在某些情况下被刻意构造的数据卡掉（碰撞概率稍高），竞赛中如果追求绝对安全，可以使用双哈希或手动取模。

生活中的例子

例子1：检查同桌的抄写作业
老师要快速判断两个同学抄写的同一段古文是否一模一样。先计算出每个同学作业的哈希值，直接比较即可。如果哈希相同，几乎可以肯定内容相同；如果不相同，一定不一样。

例子2：手机搜索“朋友圈关键词”
你在一大段文字中查找“生日快乐”这个词。如果用传统方法，需要滑动窗口逐字比较，而哈希法可以 O(1) 判断窗口内的子串是否等于目标。

例子3：判断回文
比如字符串 "racecar"，要检查整个串是否回文。可以正向哈希和反向哈希（从右到左的哈希），如果两个方向相同位置的子串哈希相同，则回文。

新手容易犯的错误

1. 忘记字符从1开始编码
   如果直接把 'a' 当作0，那么字符串 "a" 的哈希就是0，"aa" 也是0，会冲突。必须从1开始编码。

2. 下标混淆
   前缀哈希的 h[i] 对应前 i 个字符，而子串 l..r 的下标通常从1开始。代码中 get_hash(l,r) 的 l 和 r 是1-based。很多人会写成0-based，导致错误。

3. 负值取模
   当手动取模（不使用自然溢出）时，(h[r] - h[l-1]*power + mod) % mod 容易忘记加 mod 再取模，导致负数出错。

4. base 和 mod 选择不当
   base 最好大于字符集大小，且与 mod 互质。常用 base=131 或 13331，mod=1e9+7 或 1e9+9。自然溢出则 base 任选奇数即可。

5. 误认为哈希碰撞不可能发生
   即使概率极低，也可能出现两个不同字符串哈希相等的情况。竞赛中常用双哈希（两个不同的 base 和 mod）来把错误率降到几乎为零。

完整运行示例：判断字符串中有多少不同的子串

假设有字符串 "ababa"，想快速知道它有多少个不同的子串。我们可以枚举所有子串的哈希值，用集合（set）去重。

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;

typedef unsigned long long ull;
const int BASE = 131;

vector<ull> power, h;

void init_hash(const string& s) {
    int n = s.size();
    power.resize(n + 1, 1);
    for (int i = 1; i <= n; i++)
        power[i] = power[i - 1] * BASE;
    h.resize(n + 1, 0);
    for (int i = 0; i < n; i++)
        h[i + 1] = h[i] * BASE + (s[i] - 'a' + 1);
}

ull get_hash(int l, int r) {
    return h[r] - h[l - 1] * power[r - l + 1];
}

int main() {
    string s = "ababa";
    init_hash(s);
    int n = s.size();
    unordered_set<ull> seen;  // 用来存所有子串的哈希值
    for (int len = 1; len <= n; len++) {         // 枚举子串长度
        for (int l = 1; l + len - 1 <= n; l++) { // 枚举起始位置
            int r = l + len - 1;
            ull hash_val = get_hash(l, r);
            seen.insert(hash_val);
        }
    }
    cout << "不同的子串个数: " << seen.size() << endl; // 输出 9（实际子串有：a,b,ab,ba,aba,bab,ababa,baba,aba?共9个）
    return 0;
}

相关知识点指引

• KMP 算法：也是字符串匹配的经典算法，O(n+m)，但不能直接比较子串。
• Trie 树（前缀树）：可以高效存储和查找多个字符串，适合做字典。
• 后缀数组/后缀自动机：更高级的字符串处理工具，能解决更多复杂问题，但需要更多时间和空间。
• 双哈希：使用两对不同的 base 和 mod，分别计算两个哈希值，只有两个都相同才认为相等，能有效抵抗碰撞。

字符串哈希就像一把瑞士军刀，简单、快速、好用，几乎每个 OIer 都应该掌握它。下次遇到需要频繁比较子串的问题，别忘了给字符串“拍个照”哦！