CC++ & Algorithm

字符串哈希综合应用 —— 给每个字符串打上独一无二的“指纹”

困难2
语言版本：C++
概述：把字符串转换成数字，快速比较、查找重复子串或判断回文。

一秒判断两个字符串是否相同？——字符串哈希的妙用

你有没有遇到过这样的问题：班上要检查两份很长的作文有没有抄袭，如果一个个字符对比，1000字的文章要对比1000次，太慢了！或者，在编程中你需要快速知道一个字符串里有没有重复的单词——如果每次都用双重循环比较，时间就会飞涨。

字符串哈希（String Hashing）就像一个神奇的“指纹机”：给每个字符串算出一个独一无二的数字（哈希值）。如果两个字符串的哈希值相等，它们几乎就是相同的（注意！可能有极小的冲突，我们后面会讲怎么解决）。利用哈希，你可以在 O(1) 的时间里比较两个字符串是否相等，在 O(n) 的预处理后，还能快速得到任意子串的哈希值，从而实现查找重复子串、判断回文、模式匹配等操作。

下面我们就一步步来揭开这个“指纹”的秘密。

为什么要把字符串变成数字？

想象一下你和朋友各自有一个超长的字符串（比如书里的段落）。你想知道它们是否完全一样。最笨的办法是：从头到尾逐字符比较——如果字符串长度是 n，就要比较 n 次。但如果我们提前把每个字符串转化成一个整数（比如 123456789），那只需要比较两个整数是否相等，一次就够了！这就是哈希的核心思想：让复杂对象的比较变得像比较整数一样快。

生活例子：你去图书馆借书，管理员不用翻开书对比内容，只需要扫一下书脊上的条形码——每个条形码对应唯一的书。哈希值就像是字符串的“条形码”。

哈希的原理 —— 进制表示法

把字符串看作一个 某个进制下的数字。常用的进制是 131 或 31，因为它们是素数，能减少冲突。每个字符对应一个数字，比如 'a'=1, 'b'=2, ..., 'z'=26。

例如字符串 "abc"，用进制 BASE=31 计算：

哈希值 = 1×31² + 2×31¹ + 3×31⁰ = 1×961 + 2×31 + 3 = 1026

注意，我们通常用 unsigned long long（无符号 64 位整数）来存储哈希值，让它自动溢出——这相当于取模 2⁶⁴，效果是一种快速的模运算。

是不是很像将十进制数拆位：比如数字 123 = 1×10² + 2×10¹ + 3×10⁰。哈希就是换成我们自定义的进制。

快速求子串哈希 —— 前缀哈希技巧

假如我们有一个长字符串 s = "abcdefgabcd"，想知道它有没有重复的长度为 3 的子串，不可能每次截取出来重新计算整个哈希——那样太慢了。我们可以用 前缀哈希。

先定义两个数组（长度 n+1）：

  • pow[i]：存储 BASE 的 i 次方，比如 BASE^0, BASE^1, ...
  • hash[i]：存储字符串 前 i 个字符 的哈希值（即前缀哈希）

计算递推公式（假设字符从 1 开始编号）：

hash[i] = hash[i-1] * BASE + (s[i-1] - 'a' + 1);

这样，hash[3] 对应 "abc" 的哈希，hash[6] 对应 "abcdef" 的哈希。

那么，要得到子串 s[l..r]（从 0 开始的下标）的哈希，可以用公式：

子串哈希 = hash[r+1] - hash[l] * pow[r-l+1]

为什么？因为 hash[r+1] 相当于把整个前缀 [0..r] 当成一个数字，而 hash[l] 相当于前缀 [0..l-1] 的数字，但我们需要把高位的部分去掉。用减法再乘上进制幂，就可以“移走”前面部分。这个公式是哈希的核心利器，O(1) 得到任意子串的哈希。

小贴士：可以把进制想成是“位权”，就像十进制里，取后三位 12345 % 1000 = 345，但哈希用的是乘法和减法，原理类似。

实战一：查找重复子串

我们用哈希来检查一个字符串中是否存在两个相同的长度为 L 的子串。思路很简单：

  1. 计算所有前缀哈希。
  2. 从每个位置 i 开始，取长度为 L 的子串哈希，丢到一个集合（unordered_set）里。
  3. 如果发现某个哈希已经在集合中，就说明有重复子串。

下面的代码完整演示了这个过程，变量名都加上了中文注释，方便理解：

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

typedef unsigned long long ull;
const ull BASE = 131; // 常用进制，可以改成 31、1000003 等

int main() {
    string s = "abcdefgabcd"; // 原字符串
    int L = 3;                // 要找长度为 3 的重复子串

    int n = s.size();
    if (L > n) {
        cout << "没有重复" << endl;
        return 0;
    }

    // 计算前缀哈希和次方数组
    vector<ull> pow(n + 1, 1), hash(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        pow[i] = pow[i-1] * BASE;
        hash[i] = hash[i-1] * BASE + (s[i-1] - 'a' + 1); // 注意字符偏移：'a' 对应 1
    }

    unordered_set<ull> seen; // 存放已经出现过的子串哈希
    bool found = false;
    for (int i = 0; i + L <= n; i++) {
        // 计算子串 s[i..i+L-1] 的哈希
        ull curHash = hash[i + L] - hash[i] * pow[L];
        if (seen.find(curHash) != seen.end()) {
            cout << "找到重复子串: " << s.substr(i, L) << endl;
            found = true;
            break;
        }
        seen.insert(curHash);
    }
    if (!found) {
        cout << "没有重复" << endl;
    }

    return 0;
}

运行结果：字符串 "abcdefgabcd" 中有重复的 "abc"（开头和结尾都有），所以程序会输出：

找到重复子串: abc

这个技巧在字符串匹配、基因序列查找、版本比较等方面非常有用。

实战二：判断回文子串

判断一个子串是不是回文（正着读和反着读一样），比如 "abcba"。传统方法要逐字符比较，用哈希只需两次计算：

  1. 正向哈希：从前往后算，上面的方法就是正向哈希。
  2. 反向哈希：从后往前也算一遍（相当于把反转后的字符串哈希）。
    如果某个子串的正向哈希等于对应子串的反向哈希，那么它就是回文。

来举个例子，字符串 "ababa"，取整个字符串：

  • 正向哈希：'a'*BASE^4 + 'b'*BASE^3 + 'a'*BASE^2 + 'b'*BASE + 'a'
  • 反向哈希（从后往前算）：相当于把字符串反转后 "ababa" 的正向哈希，当然它和正向一样，所以是回文。

我们可以通过预处理两个哈希数组（正向和反向）来实现 O(1) 判断任意子串是否为回文。下面是完整代码（带中文注释）：

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

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

int main() {
    string s = "abcba";
    int n = s.size();

    // 正向前缀哈希
    vector<ull> pow(n + 1, 1), hash_fwd(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        pow[i] = pow[i-1] * BASE;
        hash_fwd[i] = hash_fwd[i-1] * BASE + (s[i-1] - 'a' + 1);
    }

    // 反向前缀哈希（字符串反转后）
    vector<ull> hash_rev(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        // 第 i 个字符对应反转后的位置：s[n-i]
        hash_rev[i] = hash_rev[i-1] * BASE + (s[n-i] - 'a' + 1);
    }

    // 判断子串 s[l..r] 是否为回文（下标从 0 开始）
    auto is_palindrome = [&](int l, int r) -> bool {
        int len = r - l + 1;
        ull fwd_hash = hash_fwd[r+1] - hash_fwd[l] * pow[len];
        // 反向哈希：在原字符串中区间 [l, r] 对应反转后的区间 [n-1-r, n-1-l]
        int rev_l = n - 1 - r;
        int rev_r = n - 1 - l;
        ull rev_hash = hash_rev[rev_r+1] - hash_rev[rev_l] * pow[len];
        return fwd_hash == rev_hash;
    };

    // 测试几个子串
    cout << boolalpha;
    cout << "整个字符串是回文？ " << is_palindrome(0, n-1) << endl;   // true
    cout << "子串 [1..3] (b c b) 是回文？ " << is_palindrome(1, 3) << endl; // true
    cout << "子串 [0..2] (a b c) 是回文？ " << is_palindrome(0, 2) << endl; // false

    return 0;
}

生活例子：检查一个单词是不是“回文词”，比如 “level”、“radar”，用哈希一秒搞定。

小心！哈希冲突与双哈希

哈希虽然快，但不是绝对安全——不同的字符串可能算出相同的哈希值，这叫 冲突。虽然概率很小（用 unsigned long long 自动溢出相当于模 2⁶⁴，冲突概率极低），但在竞赛中为了万无一失，我们通常使用 双哈希：用两个不同的进制（比如 131 和 1000003），分别计算两个不同的哈希值，只有两个哈希都相等才认为字符串相同。这样冲突概率几乎为零。

双哈希实现很简单：准备两套 pow 数组和 hash 数组，用两个不同的 BASE，比较时同时比较两对哈希值。

// 双哈希示例（仅片段）
typedef pair<ull, ull> hash_pair;
hash_pair get_sub_hash(int l, int r, 
                       const vector<ull>& pow1, const vector<ull>& hash1,
                       const vector<ull>& pow2, const vector<ull>& hash2) {
    int len = r - l + 1;
    ull h1 = hash1[r+1] - hash1[l] * pow1[len];
    ull h2 = hash2[r+1] - hash2[l] * pow2[len];
    return {h1, h2};
}

如果担心用 pair 比较慢，还可以用两个 unordered_set 或者直接存储 pair<ull,ull> 到 set 中。

常见错误（新手容易踩的坑）

  1. 进制选择不当：用太小的数（如 26）容易冲突，最好用大于字符集大小的素数，如 131、1000003。
  2. 字符映射从 0 开始：如果 'a' 对应 0，那么所有以 'a' 开头的字符串哈希值会一样（比如 "ab" 和 "b" ？）。一定要从 1 开始（s[i] - 'a' + 1），否则无法区分空字符。
  3. 溢出处理误解：unsigned long long 自动溢出是取模 2⁶⁴，不是无限大。但正因如此，不需要手动取模，速度更快。
  4. 忘记预计算 pow 数组：每次计算子串哈希都要用到 pow[L]，如果每次临时计算会超时。提前算好。
  5. 索引搞混：hash[i] 对应前 i 个字符（i 从 1 到 n），子串 [l, r] 的哈希用 hash[r+1] - hash[l] * pow[r-l+1]。很多人忘记加 1 或减 1。
  6. 双哈希只比较一组：只用单哈希也许能过大部分题，但万一碰巧冲突就错了。竞赛中养成用双哈希的习惯。

完整可运行示例（双哈希找重复子串）

下面给出一个完整的双哈希版本，功能仍然是查找长度为 L 的重复子串，但更加安全：

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

typedef unsigned long long ull;
const ull BASE1 = 131, BASE2 = 1000003; // 两个不同的进制
const ull MOD = 1e9 + 7; // （可选）其实 unsigned long long 自动 mod 2^64

int main() {
    string s = "abcabcxyz"; // 测试字符串
    int L = 3;              // 要查找的长度

    int n = s.size();
    if (L > n) {
        cout << "没有重复" << endl;
        return 0;
    }

    // 两个进制分别的 pow 和 hash 数组
    vector<ull> pow1(n + 1, 1), pow2(n + 1, 1);
    vector<ull> hash1(n + 1, 0), hash2(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        pow1[i] = pow1[i-1] * BASE1;
        pow2[i] = pow2[i-1] * BASE2;
        ull val = s[i-1] - 'a' + 1; // 将字符转为 1..26
        hash1[i] = hash1[i-1] * BASE1 + val;
        hash2[i] = hash2[i-1] * BASE2 + val;
    }

    // 用 pair 记录哈希对
    unordered_set<ull> seen1, seen2; // 分别存两个维度的哈希
    bool found = false;
    for (int i = 0; i + L <= n; i++) {
        ull cur1 = hash1[i + L] - hash1[i] * pow1[L];
        ull cur2 = hash2[i + L] - hash2[i] * pow2[L];
        // 判断两个哈希是否都出现过（双哈希比较）
        if (seen1.count(cur1) && seen2.count(cur2)) {
            cout << "找到重复子串: " << s.substr(i, L) << endl;
            found = true;
            break;
        }
        seen1.insert(cur1);
        seen2.insert(cur2);
    }
    if (!found) {
        cout << "没有重复" << endl;
    }
    return 0;
}

运行这个程序，你应该会看到输出：

找到重复子串: abc

相关知识点延伸

学会了字符串哈希，你可以轻松解决以下更复杂的问题：

  • 字符串匹配：通过哈希快速判断模式串是否出现在文本中（类似 KMP 但实现更简单）。
  • 最长公共子串：二分长度 + 哈希判断是否有公共子串。
  • 最长回文子串：用哈希 + 二分长度判断，比 Manacher 更容易理解。
  • 数据去重：在大数据中快速判断文件或记录是否重复。

下一步可以学习：

  • KMP（Knuth-Morris-Pratt）：另一种高效的字符串匹配算法，不用哈希但更稳定。
  • Manacher 算法：专门用于求最长回文子串，时间复杂度 O(n)。
  • 后缀数组和后缀自动机：处理更复杂的字符串问题时的高端武器。

字符串哈希是竞赛和实际开发中的“瑞士军刀”，简单、快速、灵活。现在，试着用它解决你身边的字符串问题吧！

例题精讲

1单选题

在C++中实现字符串哈希时，常使用自然溢出（unsigned long long自动取模2^64）作为哈希函数。下列关于该方法的说法中，正确的是：

A因为unsigned long long会溢出，所以两个不同字符串的哈希值一定不同
B碰撞概率极低，但理论上仍可能发生碰撞，且模数不是质数，安全性不如模大质数
C自然溢出完全避免了哈希碰撞，是竞赛中最推荐的方案
D自然溢出时，基数的选择不重要，任意值都可以
2判断题

对于任意两个不同的字符串，使用两组不同的模数（均为大质数）和基数的双哈希，可以保证绝对不发生碰撞。

3填空题
#include <bits/stdc++.h>
using namespace std;
const int base = 131;
int main() {
    string s = "ababa";
    unordered_set<unsigned long long> seen;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        unsigned long long h = 0;
        for (int j = i; j < n; j++) {
            h = h * base + (s[j] - 'a' + 1);
            seen.insert(___);
        }
    }
    cout << seen.size() << endl;
    return 0;
}
4单选题

在利用字符串哈希进行子串匹配时，通常预处理前缀哈希数组H和基数幂数组pow_base（模一个质数mod）。要计算子串s[l..r]（下标从1开始）的哈希值，正确的公式是：

A(H[r] - H[l-1] * pow_base[r-l+1]) % mod
B(H[r] - H[l-1] * pow_base[r-l]) % mod
C((H[r] - H[l-1] * pow_base[r-l+1]) % mod + mod) % mod
D(H[r] - H[l-1]) * pow_base[l-1] % mod
5判断题

在字符串哈希中，将基数base选为一个较大的质数（如131、1313）可以有效降低哈希碰撞的概率。