一、算法概述

字符串哈希是一种将字符串映射为整数值的技术，通过比较两个子串的哈希值，可以在 O(1) 时间内判断它们是否相等。广泛应用于字符串匹配、最长公共前缀、重复子串检测等场景。

---

二、核心思想

1. 进制转换思想

   • 将字符串看作一个 base 进制 的大整数。例如将 "abc" 视为：a * base² + b * base¹ + c * base⁰。
   • 通常取 base = 131 或 13331（经验值，冲突概率低）。

2. 取模防止溢出

   • 对一个大质数取模，如 MOD = 1e9 + 7 或 2⁶⁴（使用 unsigned long long 自然溢出）。
   • 单哈希可能被恶意数据卡掉，因此常采用 双哈希（两个不同 MOD）降低冲突概率。

3. 前缀哈希 + 幂数组 → O(1) 子串哈希

   • hash[i] = 前缀 s[0..i-1] 的哈希值。
   • power[i] = baseⁱ mod MOD。
   • 子串 s[l..r] 的哈希值 = hash[r+1] - hash[l] * power[r-l+1] mod MOD。

---

三、算法步骤 / 伪代码

预处理：
1. 初始化 power[0] = 1, hash[0] = 0
2. 遍历 i = 0 到 n-1：
   hash[i+1] = (hash[i] * base + s[i]) % MOD
   power[i+1] = (power[i] * base) % MOD

子串哈希查询(l, r)：
  return (hash[r+1] - hash[l] * power[r-l+1] % MOD + MOD) % MOD

---

四、C++ 代码实现

#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;
using ull = unsigned long long;

// ==================== 单哈希实现 ====================
class SingleHash {
private:
    static const ull BASE = 131;
    vector<ull> hash;   // 前缀哈希
    vector<ull> power;  // 幂数组（不使用取模，利用 unsigned long long 自然溢出，等价于 MOD = 2^64）

public:
    SingleHash(const string& s) {
        int n = s.size();
        hash.resize(n + 1, 0);
        power.resize(n + 1, 1);
        for (int i = 0; i < n; i++) {
            hash[i + 1] = hash[i] * BASE + (ull)s[i];
            power[i + 1] = power[i] * BASE;
        }
    }

    // 查询子串 s[l..r]（闭区间）的哈希值
    ull get(int l, int r) {
        return hash[r + 1] - hash[l] * power[r - l + 1];
    }
};

// ==================== 双哈希实现（更安全，抗冲突） ====================
class DoubleHash {
private:
    static const ull BASE1 = 131;
    static const ull BASE2 = 13331;
    static const ull MOD1 = 1000000007;
    static const ull MOD2 = 1000000009;

    vector<ull> hash1, hash2;
    vector<ull> power1, power2;

public:
    DoubleHash(const string& s) {
        int n = s.size();
        hash1.resize(n + 1, 0);
        hash2.resize(n + 1, 0);
        power1.resize(n + 1, 1);
        power2.resize(n + 1, 1);

        for (int i = 0; i < n; i++) {
            hash1[i + 1] = (hash1[i] * BASE1 + (ull)s[i]) % MOD1;
            hash2[i + 1] = (hash2[i] * BASE2 + (ull)s[i]) % MOD2;
            power1[i + 1] = (power1[i] * BASE1) % MOD1;
            power2[i + 1] = (power2[i] * BASE2) % MOD2;
        }
    }

    // 返回双哈希值对
    pair<ull, ull> get(int l, int r) {
        ull h1 = (hash1[r + 1] + MOD1 - hash1[l] * power1[r - l + 1] % MOD1) % MOD1;
        ull h2 = (hash2[r + 1] + MOD2 - hash2[l] * power2[r - l + 1] % MOD2) % MOD2;
        return {h1, h2};
    }

    // 判断两个子串是否相等
    bool isEqual(int l1, int r1, int l2, int r2) {
        if (r1 - l1 != r2 - l2) return false;
        return get(l1, r1) == get(l2, r2);
    }
};

// ==================== 最长重复子串（二分 + 哈希） ====================
// 返回最长重复子串（可以重叠）
string longestDupSubstring(const string& s) {
    int n = s.size();
    if (n == 0) return "";

    SingleHash sh(s);

    // 检查是否存在长度为 len 的重复子串
    auto hasDup = [&](int len) -> int {
        // 简单的哈希表检测（不处理冲突，实际场景可用更严格的方式）
        vector<ull> seen;
        for (int i = 0; i + len <= n; i++) {
            ull h = sh.get(i, i + len - 1);
            for (ull v : seen) {
                if (v == h) return i;  // 有重复，返回起始位置
            }
            seen.push_back(h);
        }
        return -1;
    };

    // 二分查找最长重复子串的长度
    int low = 1, high = n - 1;
    int bestLen = 0, bestStart = 0;
    while (low <= high) {
        int mid = (low + high) / 2;
        int pos = hasDup(mid);
        if (pos != -1) {
            bestLen = mid;
            bestStart = pos;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return s.substr(bestStart, bestLen);
}

// ==================== 测试用例 ====================
int main() {
    cout << "========== 单哈希：子串判等 ==========" << endl;
    string s1 = "hello world, hello code!";
    SingleHash sh(s1);

    // 比较两个子串是否相等
    int l1 = 0, r1 = 4;   // "hello"
    int l2 = 13, r2 = 17; // "hello"
    cout << "字符串: " << s1 << endl;
    cout << "s[" << l1 << ".." << r1 << "] = " << s1.substr(l1, r1 - l1 + 1) << ", hash = " << sh.get(l1, r1) << endl;
    cout << "s[" << l2 << ".." << r2 << "] = " << s1.substr(l2, r2 - l2 + 1) << ", hash = " << sh.get(l2, r2) << endl;
    cout << "两子串是否相等: " << (sh.get(l1, r1) == sh.get(l2, r2) ? "是" : "否") << endl;
    cout << endl;

    cout << "========== 双哈希：子串判等 ==========" << endl;
    string s2 = "abacabadabacaba";
    DoubleHash dh(s2);

    // 判断 s2[0..2] "aba" 与 s2[7..9] "aba" 是否相等
    l1 = 0, r1 = 2;
    l2 = 7, r2 = 9;
    cout << "字符串: " << s2 << endl;
    cout << "s[" << l1 << ".." << r1 << "] = " << s2.substr(l1, r1 - l1 + 1) << endl;
    cout << "s[" << l2 << ".." << r2 << "] = " << s2.substr(l2, r2 - l2 + 1) << endl;
    cout << "两子串是否相等: " << (dh.isEqual(l1, r1, l2, r2) ? "是" : "否") << endl;
    cout << endl;

    cout << "========== 最长重复子串 ==========" << endl;
    string s3 = "banana";
    cout << "字符串: " << s3 << endl;
    cout << "最长重复子串: " << longestDupSubstring(s3) << endl << endl;

    string s4 = "abcdabcd";
    cout << "字符串: " << s4 << endl;
    cout << "最长重复子串: " << longestDupSubstring(s4) << endl;

    return 0;
}

---

五、复杂度分析

复杂度类型	分析
预处理时间	O(n) — 遍历一次字符串，每次 O(1) 计算前缀哈希和幂数组。
子串哈希查询	O(1) — 只需常数次乘法和取模运算。
空间复杂度	O(n) — 需要存储哈希数组和幂数组，各 n+1 个元素。

---

六、应用场景

1. 字符串匹配：快速判断两个子串是否相等（替代 KMP 在特定场景的使用）。
2. 最长重复子串：结合二分查找，O(n log n) 找到最长重复子串。
3. 最长公共前缀 (LCP)：结合二分，O(log n) 求两个后缀的 LCP 长度。
4. 回文判断：正反哈希配合，O(1) 判断任意子串是否为回文。
5. 字符串去重与字典：为每个子串生成唯一标识。
6. Rabin-Karp 模式匹配：在文本中高效搜索模式串的出现位置。

---

七、经典例题

例题1：判断多个子串是否相等

题目描述：给定一个字符串 S 和 Q 个查询，每个查询给出 (l1, r1, l2, r2)，判断 S[l1..r1] 与 S[l2..r2] 是否相等。

解法：使用双哈希预处理，每次查询 O(1) 计算两个子串的双哈希值对，比较是否相同。

例题2：找出最长重复子串

题目描述：给定字符串 S，找出 S 中出现过至少两次的最长子串。

解法：二分答案长度 + 字符串哈希。对于每个候选长度 L，计算所有长度为 L 的子串哈希值，检查是否有重复。上述 C++ 代码中的 longestDupSubstring 函数即为此题的实现。

---

说明：以上 C++ 代码完整可编译，使用 g++ -std=c++17 -O2 filename.cpp -o main 编译后直接运行即可看到所有测试用例的输出。