前言：为什么要学字符串哈希？

正常比较两个字符串是否相同、找重复子串：逐字符对比，时间复杂度 O(n)。

哈希的终极目标：把任意字符串映射成一个数字。

从此以后：

字符串对比 = 数字对比 O(1)
字符串去重 = 数字去重
子串匹配、最长重复子串、字符串判重全部提速

哈希是字符串算法的底层基石，所有高级字符串题（二分+哈希、Rabin-Karp、后缀数组替代）都依赖它。

第一章哈希最基础：什么是多项式字符串哈希？

1.1 数学标准公式（教科书公式）

对于字符串 s0 s1 s2 ... sn-1

Hash = s0 × Bⁿ⁻¹ + s1 × Bⁿ⁻² + … + sn-1 × B⁰

B：基数（种子）
s[i]：字符的 ASCII 值

本质：把字符串当成一个「B进制的大数字」

举例（B=10）：

字符串 abc、a=1,b=2,c=3

哈希 = 1×10² + 2×10¹ + 3×10⁰ = 123

1.2 重点难点：为什么代码没有幂次？

教科书公式看着有高次幂，但代码永远写这一行：

res = res * BASE + c;

很多人卡在这里：幂次去哪里了？

👉 答案：递推自动生成幂次！不需要手动写次方！

完整模拟：字符串 abc，B=10

初始 res = 0
读 a：0*10 + 1 = 1 → 1×10⁰
读 b：1*10 + 2 = 12 → 1×10¹ + 2×10⁰
读 c：12*10 + 3 = 123 → 1×10² + 2×10¹ + 3×10⁰

每乘一次 BASE，旧字符全部升一次幂，完美等价数学公式。

这是哈希最核心的思想：左移叠加。

第二章核心必考：基数为什么必须是质数？

面试/竞赛必问：哈希种子为什么用质数？合数为什么不行？

2.1 质数的特性（131、13331）

质数：只有 1 和自身两个因数。

所有字符 ASCII（0~255）和质数几乎全部互质。

结果：哈希值分散均匀、几乎不重叠、冲突极少。

2.2 合数的致命缺陷（为什么禁用）

合数存在额外因数，会导致不同字符串算出相同哈希（哈希冲突）。

举例：B=4（合数）

字符串 22 → 2×4 + 2 = 10
字符串 16 → 1×4 + 6 = 10

完全不同的字符串 → 相同哈希值 → 程序直接判错

2.3 竞赛固定最优种子

单哈希：131
双哈希：131 + 13331（行业公认最低冲突组合）

第三章前缀哈希 + 幂次数组（哈希真正的实战核心）

普通哈希只能算整串哈希，前缀哈希可以 O(1) 求任意子串哈希，是所有竞赛题的基础。

3.1 两个核心数组作用

H[] 前缀哈希数组

H[i]：前 i 个字符的哈希值

递推公式：

H[i] = H[i-1] * B + s[i-1]

P[] 幂次数组

P[i]：B 的 i 次方（Bⁱ）

递推公式：

P[i] = P[i-1] * B

作用：位数对齐（最关键）

3.2 子串哈希万能公式（你彻底弄懂的核心）

求子串 [l, r] 哈希：

hash = H[r] – H[l-1] * P[r-l+1]

3.3 手把手举例（彻底吃透）

字符串：abcde，B=10

H[5] = 12345（整串哈希）

求子串 cde（l=3，r=5，长度=3）

H[l-1] = H[2] = 12（前面不需要的 ab）
P[3] = 1000
H[2] * P[3] = 12000 👉 把前面的字符串左移对齐高位
12345 - 12000 = 345 👉 精准得到 cde 的哈希

3.4 你之前总结的精准原话（完全正确）

前缀哈希是算整段的，我要中间一段，必须把前面不需要的部分乘上对应幂次抬高位数，和高位对齐后相减，才能精准截出子串哈希。

第四章竞赛级：单哈希缺陷 + 双哈希原理

4.1 自然溢出单哈希（入门写法）

使用 unsigned long long 存储哈希值，利用无符号整数特性：溢出自动对 \(2^{64}\) 取模。

✅ 优点：代码极简、无需手动取模、无负数问题、运算速度快

❌ 致命缺陷：模数固定为 \(2^{64}\)，算法竞赛中出题人可构造针对性数据，制造哈希碰撞，导致答案错误（WA），竞赛正式做题禁止单用。

4.2 手动取模单哈希（稳定性提升）

选用超大质数作为模数：\(10^9+7、10^9+9\)，手动对哈希结果取模，规避固定模数的被卡风险。

缺点：仍存在极低概率的哈希碰撞，无法应对竞赛极端数据。

4.3 竞赛终极方案：双哈希（100% 防碰撞）

核心思想：两套完全独立的哈希体系

第一套：基数 \(B1=131\)，模数 \(M1=10^9+7\)
第二套：基数 \(B2=13331\)，模数 \(M2=10^9+9\)

判定规则：只有两个哈希值全部相等，才判定字符串相等。

两套哈希同时发生碰撞的概率无限趋近于 0，是竞赛唯一满分、稳过的写法。

4.4 双哈希拼接原理（uint64_t 作用）

两套哈希值都是 32 位左右的整数，为了方便存储、排序、查重，将两个 32 位数值，拼接成一个 64 位整数：

// v1、v2 是两套哈希的结果
uint64_t combined = ((uint64_t)v1 << 32) | (uint64_t)v2;

uint64_t：跨平台固定 64 位无符号整数，和 unsigned long long 等价，兼容性更强
左移 32 位：把第一个哈希值放到高32位
或运算：把第二个哈希值放到低32位
最终：一个数字存储两套哈希，极大简化后续查重逻辑

第五章核心重难点：check 函数超详细精讲（小白必懂）

5.1 check 函数核心作用

传入一个长度 mid，判断：原字符串中是否存在两个完全相同、长度为 mid 的子串

存在重复子串 → 返回 true（该长度可行，可尝试更长）
无重复子串 → 返回 false（该长度不可行，需要缩短）

是「二分答案 + 哈希」求最长重复子串的核心验证函数。

5.2 完整工作流程（四步走）

第一步：遍历所有长度为 mid 的子串，计算双哈希值

字符串长度为 L，长度为 mid 的子串总个数：\(L-mid+1\) 个，逐个截取子串、通过前缀哈希公式算出唯一拼接哈希值。

第二步：存储所有子串哈希值

用 vector 存储所有哈希值，统一管理。

第三步：排序

重复的哈希值，排序后一定会相邻排列。

💡 核心对比：

未排序：需要双层循环两两对比，复杂度 \(O(n^2)\)，大数据直接超时
排序后：只需单层遍历相邻元素，复杂度 \(O(n\log n)\)，竞赛最优解

第四步：遍历查重

遍历排序后的哈希数组，发现相邻相等的值 = 存在重复子串。

5.3 极简实例模拟（肉眼看懂）

示例字符串：ababa，L=5，mid=2（检查是否有长度为2的重复子串）

所有子串：ab、ba、ab、ba

对应哈希值：H1、H2、H1、H2

存储数组：[H1, H2, H1, H2]

排序后数组：[H1, H1, H2, H2]

遍历发现相邻 H1 相等 → 存在重复 → 返回 true

5.4 关键代码行精讲（你困惑的核心）

long long v1 = (H1[i + mid - 1] - H1[i - 1] * P1[mid]) % M1;

H1[i+mid-1]：当前子串结尾位置的前缀哈希（完整长哈希）
H1[i-1]：子串前面、需要舍弃的前缀哈希
P1[mid]：幂次对齐，把舍弃的前缀哈希抬到高位，和长哈希位数统一
相减后：精准剔除前置无效部分，得到纯子串哈希

5.5 负数修正的原因

C++ 中负数取模结果仍为负数，会导致哈希值错乱、判重错误。

所以需要手动修正：if (v1 < 0) v1 += M1;

第六章竞赛C++细节精讲（所有坑全覆盖）

6.1 hashes.reserve() 作用

vector 默认空容器，添加元素时会动态扩容、拷贝数据，大数据量下极度耗时（TLE元凶）。

reserve(n)：提前预分配 n 个空间，杜绝动态扩容，纯性能优化，竞赛必备。

6.2 size_t 详解（解决编译警告）

1、什么是 size_t？

C++ 官方无符号整数类型，专门用来存储容器长度、数组大小、下标。

2、为什么 int 会报警告？

vector.size() 返回值是 size_t（无符号），用 int（有符号）变量对比，类型不匹配，编译器强制警告。

3、使用规则（必背）

只要遍历 vector、string、数组长度，循环变量一律用 size_t。

6.3 为什么不用 unordered_set 查重？

很多新手误区：觉得 unordered_set 是 O(1) 更快。

实际竞赛真相：

unordered_set 常数极大，存在哈希冲突、重哈希、扩容开销
2e5 数据量下，vector+sort 速度远快于 unordered_set

结论：字符串哈希查重，固定用 vector+sort，绝不使用 unordered_set。

第七章两大哈希体系对比（选型标准）

哈希类型	优点	缺点	适用场景
自然溢出单哈希	代码极简、无取模、速度快	可被构造数据卡碰撞	日常练习、简单程序、非竞赛场景
双哈希手动取模	零碰撞、绝对稳定、不被卡数据	代码稍多、需要修正负数	所有算法竞赛、正式做题、满分场景

第八章竞赛满分完整模板（可直接提交AC）

适配最长重复子串问题，无警告、无TLE、无WA，标准赛场写法

#include <bits/stdc++.h>
using namespace std;
const int MAXL = 200005;

// 双哈希模数（大质数）
const long long M1 = 1e9 + 7;
const long long M2 = 1e9 + 9;
// 双哈希基数（低冲突质数）
const long long B1 = 131;
const long long B2 = 13331;

// 前缀哈希、幂次数组
long long H1[MAXL], H2[MAXL];
long long P1[MAXL], P2[MAXL];

int L;
string S;

// 校验长度mid是否存在重复子串
bool check(int mid) {
    vector<uint64_t> hashes;
    hashes.reserve(L - mid + 1);
    
    for (int i = 1; i <= L - mid + 1; ++i) {
        // 第一套哈希计算
        long long v1 = (H1[i + mid - 1] - H1[i - 1] * P1[mid]) % M1;
        if (v1 < 0) v1 += M1; 
        // 第二套哈希计算
        long long v2 = (H2[i + mid - 1] - H2[i - 1] * P2[mid]) % M2;
        if (v2 < 0) v2 += M2;
        
        // 拼接双哈希
        uint64_t combined = ((uint64_t)v1 << 32) | (uint64_t)v2;
        hashes.push_back(combined);
    }
    
    // 排序查重
    sort(hashes.begin(), hashes.end());
    for (size_t i = 1; i < hashes.size(); ++i) {
        if (hashes[i] == hashes[i - 1]) {
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> L >> S;
    
    // 预处理幂次和前缀哈希
    P1[0] = P2[0] = 1;
    for (int i = 1; i <= L; ++i) {
        P1[i] = (P1[i-1] * B1) % M1;
        P2[i] = (P2[i-1] * B2) % M2;
        H1[i] = (H1[i-1] * B1 + S[i-1]) % M1;
        H2[i] = (H2[i-1] * B2 + S[i-1]) % M2;
    }
    
    // 二分答案
    int l = 1, r = L - 1, ans = 0;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

第九章全套核心知识点终极总结（可直接背诵）

9.1 哈希底层原理

字符串哈希 = 多项式进制映射，res = res*B + c 递推自动生成幂次，等价于标准数学公式。

9.2 基数核心规则

基数必须用质数（131/13331），合数会导致哈希冲突，绝对禁用。

9.3 两大数组作用

H[]：前缀哈希数组，存储前i个字符哈希值
P[]：幂次数组，用于位数对齐，实现O(1)截取子串哈希

子串哈希公式：hash = H[r] - H[l-1] * P[len]

9.4 竞赛保命规则

竞赛必须用双哈希手动取模，杜绝碰撞WA
查重固定 vector+sort，拒绝 unordered_set 防止TLE
容器遍历用 size_t，消除编译警告
取模后负数必须手动修正，保证哈希值合法

9.5 check函数核心逻辑

遍历所有同长度子串→计算双哈希→排序对齐重复值→遍历查重，配合二分找到最长合法重复子串。

题目：

COCI ’06 Contest 5 #6 Dvaput：题目页确认它是 DMOJ 上的真实题目，类型是 String Algorithms，官方 editorial 直接用 Rabin-Karp / rolling hash 讲解。很适合当作经典入门题。
CCC ’20 S3 – Searching for Strings：题目页确认存在，官方 editorial 明确写到用 rolling hash 来维护滑动窗口并比较子串。适合练“窗口 + 哈希 + 去重”。
COCI ’15 Contest 5 #5 OOP：题目页确认它是 Data Structures, String Algorithms 题，官方 editorial 里明确说到可以用 hashing 快速比较前缀和后缀，再配合 Trie / DFS 做查询。
COI ’15 #2 Palinilap：题目页确认存在，官方 editorial 明确提到用 rolling hash 做子串相等判断，再配合二分处理回文相关计算。适合练“二分答案 + 子串哈希”。
DMOPC ’20 Contest 5 P6 – Top Row：题目页确认存在，类型是 Data Structures, String Algorithms；官方 editorial 里提到可以用 hash set 维护不同子串的 hash 值。这个更偏“区间子串去重”。
CEOI ’17 P5 – Palindromic Partitions：题目页确认存在，官方 editorial 明确写到用 rolling hashes 优化字符串比较。这个比前面几题更进阶，适合练回文分割类 DP / 构造思路。
COCI ’16 Contest 4 #6 Osmosmjerka：题目页确认存在，类型是 String Algorithms；官方 editorial 明确使用 hash function 和 rolling hash 来统计不同字符串出现次数。它更偏综合题，难度会高一些。

String Hash字符串哈希