字符串哈希 (String Hash)¶

字符串多项式哈希将任意子串映射为一个整数值，使得我们能在 \(\mathcal{O}(1)\) 时间内比较任意两个子串是否相同。

防 Hack 双哈希模版 (推荐)¶

在 Codeforces 等对常数模数有针对性 Hack 数据的平台上，单模数哈希（甚至自然溢出 \(2^{64}\)）极易被构造冲突数据。强烈建议比赛中使用双哈希 (Double Hash)，碰撞概率约为 \(\mathcal{O}(\frac{1}{M_1 M_2}) \approx 10^{-18}\)。

#include <vector>
#include <string>

struct DoubleHash {
    static constexpr long long MOD1 = 1e9 + 7;
    static constexpr long long MOD2 = 1e9 + 9;
    static constexpr long long BASE1 = 131;
    static constexpr long long BASE2 = 13331;

    int n;
    std::vector<long long> h1, h2;
    std::vector<long long> p1, p2;

    DoubleHash(const std::string &s) : n(s.size()) {
        h1.assign(n + 1, 0);
        h2.assign(n + 1, 0);
        p1.assign(n + 1, 1);
        p2.assign(n + 1, 1);

        for (int i = 0; i < n; ++i) {
            h1[i + 1] = (h1[i] * BASE1 + s[i]) % MOD1;
            h2[i + 1] = (h2[i] * BASE2 + s[i]) % MOD2;
            p1[i + 1] = (p1[i] * BASE1) % MOD1;
            p2[i + 1] = (p2[i] * BASE2) % MOD2;
        }
    }

    // 获取子串 s[l...r] 的双哈希值 (0 <= l <= r < n)
    std::pair<long long, long long> get(int l, int r) const {
        long long res1 = (h1[r + 1] - h1[l] * p1[r - l + 1]) % MOD1;
        if (res1 < 0) res1 += MOD1;

        long long res2 = (h2[r + 1] - h2[l] * p2[r - l + 1]) % MOD2;
        if (res2 < 0) res2 += MOD2;

        return {res1, res2};
    }
};

避坑指南¶

自然溢出 unsigned long long 的风险：由于模数固定为 \(2^{64}\)，且在 Thue-Morse 序列下存在已知的多项式哈希杀手数据（Killer Testcase），在 Codeforces 平台上单用 ull 极易被 Hack。
随机 Base：若使用单哈希，建议使用 std::mt19937_64 随机生成大于字符集范围的一个质数作为 BASE，能够显著降低被针对的风险。

LeetCode 经典真题精选与题解提示¶

LeetCode 187 - 重复的DNA序列 (Repeated DNA Sequences) 中等
提示

定长滑动窗口哈希。
- DNA 序列长度固定为 10，仅含 4 种字符（A, C, G, T），可用 2 位二进制表示一个字符。
- 维护长度为 10 的滑动窗口，等价于一个 20 位的二进制整数，在 \(\mathcal{O}(1)\) 时间内位移更新哈希值，结合哈希表计数去重。
LeetCode 1044 - 最长重复子串 (Longest Duplicate Substring) 困难
提示

二分长度 + 字符串双哈希 (Rabin-Karp)。
- 重复子串的长度具有二分单调性：若存在长度为 \(L\) 的重复子串，则长度 \(< L\) 的子串必然也存在重复。
- 在 \([1, n - 1]\) 上二分长度 \(L\)。利用字符串哈希（推荐双哈希或大素数哈希避免碰撞）在 \(\mathcal{O}(n)\) 时间内检验是否存在至少出现 2 次的长度为 \(L\) 的子串，总体复杂度 \(\mathcal{O}(n \log n)\)。
LeetCode 1062 - 最长重复子串 (Longest Repeating Substring) 中等
提示

二分答案与滚动哈希基石。
- 相比 LC 1044 数据范围更小（\(n \le 1500\)），检验二分长度 \(L\) 时用滚动哈希记录所有长为 \(L\) 的子串哈希值到 unordered_set 中，一旦发现重复即说明合法。
LeetCode 2156 - 查找给定哈希值的子串 (Find Substring With Given Hash Value) 困难
提示

倒序滑动窗口滚动哈希。
- 题目的哈希定义采用正向递增幂次：\(hash = \sum_{i=0}^{k-1} val(s[l + i]) \times p^i \pmod m\)。若正向滑动窗口，每次需要做除法求逆元。
- 倒序从右向左滑动窗口：新进入左端点的字符刚好处于 \(p^0 = 1\) 的位置，更新公式为 \(hash = (hash \times p + val(s[i]) - val(s[i + k]) \times p^k) \pmod m\)，避开模逆元操作，实现严格 \(\mathcal{O}(n)\) 滑窗。