C++字符串哈希算法详解：原理、模板与竞赛实战

1. 项目概述：为什么我们需要字符串哈希？

在C++算法竞赛和日常开发中，处理字符串匹配、子串比较这类问题简直是家常便饭。最朴素的想法就是直接逐字符比较，但它的时间复杂度是O(n)，当数据量一大，比如要在百万级别的文本里反复查询子串，这种暴力方法就完全不够看了。这时候，字符串哈希（String Hashing）就闪亮登场了。它本质上是一种将任意长度的字符串映射成一个固定长度整数的技术，这个整数我们称之为哈希值。一旦我们有了这个“数字指纹”，比较两个字符串是否相等就退化成了比较两个整数是否相等，时间复杂度瞬间降到O(1)。

听起来是不是有点像“黑魔法”？我第一次接触时也觉得神奇。但它的核心思想其实很朴素：把字符串看作一个K进制的数。比如字符串“abc”，我们可以把它看成是(‘a’ * K² + ‘b’ * K + ‘c’)这样一个数字。当然，为了防止这个数字过大溢出，我们会对一个很大的质数取模。这样，每个字符串就对应了一个唯一的（在大概率上）哈希值。字符串哈希的威力不仅在于快速比较，它结合前缀和思想后，可以O(1)地获取任意子串的哈希值，这才是它解决复杂问题的关键。

这个模板适合所有正在学习C++数据结构与算法，尤其是准备技术面试或算法竞赛的同学。无论你是想搞懂原理，还是急需一个稳定、高效的代码模板来应对笔试，接下来的内容都会给你掰开揉碎了讲清楚。

2. 字符串哈希的核心原理与设计思路

2.1 进制与模数的选择：安全的基石

字符串哈希的可靠性，几乎完全建立在进制（base）和模数（mod）的选择上。这不是随便选两个数就行，里面大有学问。

首先说进制base。它必须大于字符集的大小。对于常见的包含大小写字母和数字的字符串，字符集大小超过60，所以base通常选择一个大于60的质数，比如131, 13331, 1313131等。选择质数是为了让字符串的每一位对最终哈希值的贡献尽可能均匀，减少冲突。我个人的经验是，在算法竞赛中，131和13331是经过无数人验证的“黄金数字”，出题人一般不会针对这两个数设计卡哈希的数据。

然后是模数mod。这是整个哈希系统的“天花板”。为了防止溢出，我们计算出的K进制数需要对一个模数取余。模数必须足够大，以减少不同字符串映射到同一个哈希值的概率（即哈希冲突）。同时，为了计算效率，我们通常选择一个大质数，或者利用C++unsigned long long的自然溢出（相当于对2^64取模）。

注意：自然溢出法虽然写起来简单，且速度最快（因为CPU自动处理溢出），但存在被精心构造的数据攻击（哈希碰撞）的风险。在严肃的算法竞赛中，如果担心被卡，建议使用双哈希（即用两个不同的base和mod计算两个哈希值，只有当两个值都相等时才认为字符串相等）。

2.2 前缀哈希数组的构建

理解了单个字符串的哈希计算，我们如何快速得到任意子串的哈希值呢？答案是：前缀哈希。

我们预处理一个数组h[]，其中h[i]表示字符串s从第1个字符到第i个字符（假设字符串下标从1开始）组成的子串的哈希值。同时，我们预处理一个数组p[]，其中p[i]表示base的 i 次方。

那么，h[i]可以通过递推公式轻松得到：h[i] = (h[i-1] * base + s[i]) % mod。这里s[i]是字符，通常我们取其ASCII码值。

这个公式怎么理解？假设我们已经知道前 i-1 个字符的哈希值h[i-1]，它相当于一个K进制的数。现在要在它后面“拼接”上第 i 个字符s[i]，那么新的数就是h[i-1] * base + s[i]。乘以base相当于把原来的数整体左移了一位（在K进制下），然后加上新的低位。

2.3 子串哈希值的提取公式

这是字符串哈希最精华的部分。假设我们想要求字符串s中从第l个字符到第r个字符的子串的哈希值。

我们已经有了：

• h[r]：代表s[1...r]的哈希值，其数值为(s[1]*base^{r-1} + s[2]*base^{r-2} + ... + s[r]*base^{0})
• h[l-1]：代表s[1...l-1]的哈希值，其数值为(s[1]*base^{l-2} + s[2]*base^{l-3} + ... + s[l-1]*base^{0})

我们想要的s[l...r]的哈希值，应该是(s[l]*base^{r-l} + s[l+1]*base^{r-l-1} + ... + s[r]*base^{0})

观察一下，h[r]这个多项式里，包含了我们想要的s[l...r]部分，但也包含了我们不想要的s[1...l-1]部分，而且它们的“权重”（即base的指数）不同。为了去掉s[1...l-1]部分，我们需要将h[l-1]这个多项式“对齐”到和h[r]中对应部分相同的指数权重上。

怎么做？将h[l-1]乘以base^{r-l+1}。这样，h[l-1] * p[r-l+1]就变成了(s[1]*base^{r-1} + s[2]*base^{r-2} + ... + s[l-1]*base^{r-l+1})。

现在，用h[r]减去这个对齐后的值：h[r] - h[l-1] * p[r-l+1] = (s[l]*base^{r-l} + ... + s[r]*base^{0})

这正是我们想要的子串哈希值！考虑到取模运算，最终的公式为：hash(s[l...r]) = (h[r] - h[l-1] * p[r-l+1] % mod + mod) % mod

加上mod再取模是为了防止减法出现负数，这是一个标准的安全写法。

3. 模板代码实现与逐行解析

下面我将给出一个最常用、最稳定的字符串哈希模板，采用自然溢出法（模数为2^64），并附上超详细的注释。这个模板可以直接用于解决绝大多数问题。

#include <iostream> #include <string> #include <vector> using namespace std; typedef unsigned long long ULL; // 使用unsigned long long，利用其自然溢出特性，自动对2^64取模 const int N = 100010; // 根据题目字符串最大长度调整 const int base = 131; // 经验证常用的质数进制 ULL h[N]; // 前缀哈希数组，h[i]表示s[1..i]的哈希值 ULL p[N]; // 存储base的幂，p[i] = base^i char s[N]; // 输入的字符串，下标从1开始 // 初始化函数，计算前缀哈希数组h和幂数组p void init() { p[0] = 1; // base^0 = 1 h[0] = 0; // 空字符串的哈希值为0 // 假设字符串s已经从下标1开始存储 for (int i = 1; s[i]; i++) { // 遍历字符串直到结束符 h[i] = h[i - 1] * base + s[i]; // 核心递推公式：前i-1位的哈希值左移一位，加上当前字符 p[i] = p[i - 1] * base; // 计算base的i次方 } } // 查询函数：获取子串s[l..r]的哈希值 (l和r为闭区间，且从1开始计数) ULL get_hash(int l, int r) { // 核心公式：h[r] - h[l-1] * p[r-l+1] // 利用ULL自然溢出，减法结果若为负数会自动加上2^64，等同于取模后的正数 return h[r] - h[l - 1] * p[r - l + 1]; } int main() { // 示例：读入字符串并初始化 scanf(“%s”, s + 1); // 从s[1]开始存储字符串 init(); // 示例：查询多个子串是否相等 int l1, r1, l2, r2; while (cin >> l1 >> r1 >> l2 >> r2) { if (get_hash(l1, r1) == get_hash(l2, r2)) { cout << “Yes” << endl; } else { cout << “No” << endl; } } return 0; }

关键代码行解析：

1. typedef unsigned long long ULL;： 这是自然溢出法的关键。ULL的范围是0到2^64-1，当乘法或加法结果超过这个范围时，会发生环绕（wrap-around），即自动对2^64取模。这省去了显式取模运算，速度更快。
2. h[i] = h[i - 1] * base + s[i];： 这是构建前缀哈希的核心。h[i-1] * base相当于将前i-1个字符的哈希值这个“K进制数”整体左移一位（高位），然后加上当前字符s[i]作为新的最低位。
3. return h[r] - h[l - 1] * p[r - l + 1];： 这是提取子串哈希值的灵魂。h[l-1] * p[r-l+1]将前缀s[1..l-1]的哈希值提升到与s[1..r]中对应部分相同的“数量级”（即K进制下的相同高位），相减之后，高位抵消，剩下的就是纯粹的子串s[l..r]的哈希值。由于是ULL运算，减法若为负会自然溢出成正数，效果等同于(h[r] - h[l-1]*p[r-l+1] % MOD + MOD) % MOD。

实操心得： 很多新手在这里会困惑为什么是p[r-l+1]而不是p[r-l]。记住一个技巧：区间的长度是len = r - l + 1。我们需要将h[l-1]乘以base^len，才能让它“追上”h[r]中对应部分的位置。把这个长度记牢，公式就不会错了。

4. 经典例题实战：解决重复子串问题

理论讲得再多，不如实战一把。我们来看一个经典问题：“最长重复子串”。给定一个字符串，找到其中最长的、至少出现两次的连续子串。如果没有，返回0。

问题分析： 暴力枚举所有子串并两两比较，复杂度是O(n^4)，不可行。字符串哈希给我们提供了快速比较子串的能力。一个常见的思路是二分答案 + 哈希。

思路：

1. 答案（最长长度）具有单调性：如果长度为L的子串可以重复出现，那么长度小于L的子串也一定可以（取它的前缀即可）。因此我们可以二分查找这个长度L。
2. 在二分检查函数check(len)中，我们遍历字符串所有长度为len的子串，计算它们的哈希值，并存入一个哈希表（如C++的unordered_set或unordered_map）。
3. 如果在遍历过程中，发现某个哈希值已经存在于集合中，说明我们找到了一个重复出现的、长度为len的子串，函数返回true。
4. 如果遍历完都没找到重复，则返回false。

代码实现：

#include <iostream> #include <string> #include <unordered_set> #include <algorithm> using namespace std; typedef unsigned long long ULL; const int N = 100010; const int base = 131; ULL h[N], p[N]; char s[N]; int n; // 字符串长度 void init() { p[0] = 1; h[0] = 0; for (int i = 1; i <= n; i++) { h[i] = h[i - 1] * base + s[i]; p[i] = p[i - 1] * base; } } ULL get_hash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } // 检查是否存在长度为len的重复子串 bool check(int len) { if (len <= 0) return false; unordered_set<ULL> seen; // 遍历所有起始位置为i，长度为len的子串 for (int i = 1; i + len - 1 <= n; i++) { int j = i + len - 1; ULL sub_hash = get_hash(i, j); if (seen.count(sub_hash)) { return true; // 找到了重复的哈希值 } seen.insert(sub_hash); } return false; } int main() { scanf(“%s”, s + 1); n = strlen(s + 1); init(); // 二分查找最大长度 int l = 0, r = n; // 答案可能为0到n while (l < r) { int mid = (l + r + 1) >> 1; // 向上取整，避免死循环 if (check(mid)) { l = mid; // 长度mid可行，尝试更大的 } else { r = mid - 1; // 长度mid不可行，减小 } } cout << l << endl; // 输出最长重复子串长度 return 0; }

复杂度分析： 二分复杂度为O(log n)，每次check需要遍历O(n)个子串并计算哈希（O(1)），插入和查询哈希表平均O(1)。因此总时间复杂度为O(n log n)，相比暴力解法是巨大的优化。

避坑指南： 在这个问题中，哈希冲突有可能导致误判（即两个不同的长度为len的子串哈希值相同，我们误以为找到了重复）。在算法竞赛中，如果担心被卡，有几种策略：

1. 使用双哈希：用两个不同的base和mod（或自然溢出）分别计算哈希值，只有当两个哈希值都相等时才认为子串相等。这能将冲突概率降到极低。
2. 在哈希值冲突时进行二次验证：当发现哈希值重复时，并不立即返回true，而是记录下位置，最后再对这些候选位置进行直接的字符串比较（strcmp）。因为冲突通常很少，所以实际开销不大。

5. 字符串哈希的进阶应用与变形

掌握了基础模板和二分哈希的思路，我们可以解决一大类字符串问题。下面再介绍几个典型应用场景。

5.1 判断回文子串

传统判断回文需要O(n)时间。结合哈希，我们可以预处理原串和反串的哈希数组，然后对于任意子串s[l..r]，我们可以O(1)得到它和它的反转串的哈希值并进行比较。这常用于需要多次查询子串是否回文的场景。

思路：

1. 预处理原字符串s的前缀哈希数组h1[]。
2. 预处理反转字符串s’的前缀哈希数组h2[]。
3. 对于查询[l, r]，原串子串哈希为get_hash(h1, l, r)。
4. 其在反串中的对应位置是[n-r+1, n-l+1]，哈希值为get_hash(h2, n-r+1, n-l+1)。
5. 比较两者是否相等。

5.2 字符串拼接与修改的哈希维护

有些问题涉及动态的字符串，比如在末尾添加字符，或者修改某个位置的字符。我们能否快速维护整个字符串的哈希值呢？

• 末尾添加字符： 这是最简单的。设当前字符串长度为len，哈希值为cur_hash，新字符为c。则新的哈希值new_hash = cur_hash * base + c。我们的前缀哈希数组h本身就是这么递推维护的。
• 修改某个位置的字符： 这相对复杂。假设将位置i的字符从old_c改为new_c。这次修改会影响所有包含位置i的子串的哈希值，即所有h[j](j >= i)。如果直接重新计算，成本是O(n)。在需要频繁修改的场景下（如某些数据结构题），这就需要结合更高级的数据结构，如线段树来维护区间哈希值，从而支持单点修改和区间哈希查询。

5.3 双哈希模板实现

对于需要高安全性的场景，这里给出一个双哈希的模板。它使用两个不同的基数和模数，只有当两个哈希值都相等时才认为字符串相等。

#include <iostream> #include <string> #include <utility> // for pair using namespace std; typedef long long LL; const int N = 100010; const int base1 = 131, base2 = 13331; const int mod1 = 1e9 + 7, mod2 = 1e9 + 9; // 两个大质数模数 LL h1[N], h2[N], p1[N], p2[N]; char s[N]; void init() { p1[0] = p2[0] = 1; for (int i = 1; s[i]; i++) { h1[i] = (h1[i-1] * base1 + s[i]) % mod1; h2[i] = (h2[i-1] * base2 + s[i]) % mod2; p1[i] = (p1[i-1] * base1) % mod1; p2[i] = (p2[i-1] * base2) % mod2; } } // 返回一个pair，包含两个哈希值 pair<LL, LL> get_hash(int l, int r) { LL hash1 = (h1[r] - h1[l-1] * p1[r-l+1] % mod1 + mod1) % mod1; LL hash2 = (h2[r] - h2[l-1] * p2[r-l+1] % mod2 + mod2) % mod2; return {hash1, hash2}; } // 比较两个子串是否相等 bool is_equal(int l1, int r1, int l2, int r2) { auto hash_a = get_hash(l1, r1); auto hash_b = get_hash(l2, r2); return hash_a.first == hash_b.first && hash_a.second == hash_b.second; }

使用双哈希后，哈希冲突的概率从大约1/mod降低到了1/(mod1*mod2)，对于模数在1e9级别的，冲突概率极低，可以认为是安全的。

6. 常见问题、调试技巧与性能优化

6.1 哈希冲突：理论与应对

哈希冲突是指两个不同的字符串产生了相同的哈希值。在自然溢出法中，模数是2^64，冲突概率已经很低，但并非为零。在正式比赛中，有经验的出题人可能会构造“哈希碰撞”的数据来卡掉自然溢出法的单哈希。

如何判断自己被卡哈希了？如果你的程序在逻辑完全正确的情况下，在某个测试点上得到了错误的答案（尤其是WA而不是TLE），而该测试点字符串很长且查询很多，就很可能是哈希冲突。

解决方案：

1. 换用更强的哈希参数： 尝试更换base值，例如使用1313131或19260817等更大的质数。有时出题人只针对常见的131和13331。
2. 使用双哈希： 如上文所示，这是最根本的解决方法。几乎可以杜绝竞赛中的数据攻击。
3. 使用三哈希或组合哈希： 在极端情况下（如对安全性要求极高的系统），可以使用更多组哈希。但在竞赛中，双哈希足矣。

6.2 初始化与下标处理易错点

1. 下标从1开始： 模板中为了公式简洁，通常让字符串下标从1开始。scanf(“%s”, s + 1)是实现这一点的常用方法。务必注意，此时strlen(s)不能用了，因为s是char*类型，s和s+1地址不同。正确获取长度应用strlen(s + 1)或用一个变量在读取时记录。
2. p[0]和h[0]的初始化：p[0] = 1和h[0] = 0必须正确设置。p[0]=1是因为任何数的0次方为1。h[0]=0代表空串哈希值为0。
3. 区间边界判断： 在get_hash(l, r)函数中，务必确保调用时1 <= l <= r <= n。在循环中，子串结束位置j = i + len - 1要判断j <= n。

6.3 性能优化与小技巧

1. 使用unsigned long long自然溢出： 这比显式取模（%）运算要快得多，是竞赛中的首选。担心冲突就用双哈希。
2. 预处理幂数组p： 在初始化时一次性计算好p[]数组，避免在每次调用get_hash时重复计算base的幂。
3. 减少函数调用开销： 如果追求极致性能，可以将get_hash函数写成宏或内联函数。对于双哈希，可以写一个返回pair的函数，但多次调用可能有一定开销，在超高频查询时可以考虑分别计算两个哈希值。
4. 空间换时间：h和p数组通常开成全局变量，大小根据题目数据范围设定（如N=1e6+10）。避免在函数内开大数组导致栈溢出。

6.4 字符串哈希 vs 其他字符串算法

字符串哈希常被拿来与KMP、后缀数组等算法比较。

• vs KMP： KMP用于单模版串匹配问题（找一个模式串在文本串中的所有出现位置）是O(n+m)的，比哈希更“标准”。哈希的优势在于可以O(1)比较任意两个子串是否相等，功能更通用，比如解决“最长重复子串”、“回文子串查询”等问题更方便。
• vs 后缀数组： 后缀数组是字符串处理的“重型武器”，能解决几乎所有后缀相关的问题（如不同子串个数、最长公共前缀等），功能比哈希强大，但原理和实现也复杂得多。字符串哈希实现简单，在解决特定子串比较问题上代码短、易调试，是竞赛中的一把“快刀”。

选择建议： 如果问题核心是快速比较任意两个子串是否相等，或者需要二分答案结合子串比较，字符串哈希通常是首选。如果是标准的字符串匹配问题，KMP更合适。如果需要处理非常复杂的后缀结构问题，则学习后缀数组。

我个人在刷题和比赛时，字符串哈希是我最常备的工具之一。它的简洁和高效，让我在面对字符串问题时总能多一个清晰的思路。记住模板，理解原理，然后大胆地去应用和变形，你会发现很多看似困难的字符串问题都迎刃而解了。最后再强调一遍，在关键比赛中，如果对安全性有疑虑，双哈希是你的不二之选。