★ FEATURED ARTICLE 1. 模拟赛被质疑之后我重新把字符串哈希从头捋了一遍有次模拟赛题目给了一个长度不小的字符串要求回答若干组“两个区间是否完全相同”的询问。数据范围压得很死暴力比对显然不行我当时直接用字符串哈希在 O(1) 时间内回答了每一组询问。赛后有人提了一嘴“你确定哈希不会撞吗”当时我嘴上说概率极低回去自己翻公式发现里面有很多细节没真正想清楚。也正是这次复盘让我把这套方法彻底内化了。这篇内容就是那次复盘之后的整理适合刚学会字符串哈希想用得更稳的新手也适合准备竞赛进阶、需要系统掌握哈希用法与坑点的选手。1.1 为什么竞赛里到处都要用到它要说清字符串哈希先看它解决的问题。最朴素的两个字符串比较是逐字节比慢的时候要 O(n)KMP、字典树这类算法能解决匹配和前缀统计但都对结构有限制——KMP 只能做单模式匹配字典树只能按前缀组织。可比赛题目经常问的是“任意两个位置开头的相同长度子串是否相等”“某个子串是不是另一个子串的循环节”“一个区间内的文本重复了几次”这类问题字符串哈希几乎是唯一能把这些问题变成整数加减的通用工具。它把字符串变成一串“指纹”任意子串的指纹都能在 O(1) 时间内拿到比较两个指纹就是比较两个整数。整数比较就只是 CPU 一条指令的事大量字符串操作被压到近乎常数的成本。而且它不像后缀数组、后缀自动机那样需要背大量模板和边界条件原理就几条公式写起来非常快。竞赛里很多字符串题第一步想到的解法往往就是哈希能用哈希暴力过掉一大半。1.2 一句话概括核心思想把字符串看成一个 base 进制下的整数。字符就是数字位只不过进制不是 10而是你自己选的 base通常 131、13331。比如 “abc” 如果 a1、b2、c3base10那么值就是 1*10^2 2*10^1 3 123。换成更大的 base就是为了让不同字符串几乎不会映射到同一个数。这个“数”在内存里肯定放不下所以还要取模。取模之后“碰撞”两个不同字符串碰巧得到相同余数就成了唯一要担心的数学风险。后续所有优化其实都是在围绕“怎么把碰撞概率压到可以忽略”来做文章。我不喜欢用太学术的语言去定义它上面这个理解足够支撑后面所有推导。接下来直接拆公式、给模板、讲应用最后再把踩过的坑一个个列出来。2. 多项式哈希的数学原理与三行核心公式2.1 前缀哈希怎么递推假设字符串 s 的下标从 1 开始长度是 n。选一个质数作为模数 M选一个大于字符集规模的 base。定义前缀哈希h[0] 0 h[i] (h[i-1] * base val(s[i])) % M其中 val(s[i]) 是把字符映射成整数的函数这个映射至少要保证所有字符的值都大于 0具体原因后面会讲。这个递推式相当于每读一个字符就把前面的数字整体“左移”一位再填上新的数字。字符串处理完之后整个串的哈希就是那个进制数的余数表示。用生活化的方式理解它就像一个滚动行李箱的密码锁每来一个字符你先把所有轮子都拧到高位再在最低位拨入新字符的数字。只要进制选得够大、模数选得够好不同字符串开出来的密码几乎不会相同。2.2 任意子串的哈希怎么 O(1) 求真正方便的是 h[r] 与 h[l-1] 之间隐藏着子串的值。观察一下前缀之间的关系h[r] h[l-1] * base^(r-l1) 子串 [l..r] 的哈希值这个式子的原理是h[r] 是从开头到 r 的完整数字其中前面 l-1 位已经被左移了 r-(l-1) 位也就是乘了 base^(r-l1)。把这一部分从 h[r] 里减掉剩下的自然就是子串本身。于是得到最核心的公式子串哈希 (h[r] - h[l-1] * base^(r-l1) M) % M这里的 base^(r-l1) 要提前预处理成幂数组查询时一次乘法、一次减法、一次取模O(1) 完成。很多人刚开始会把子串再单独算一遍那就完全失去了哈希的意义。记住这条公式后面所有应用都靠它。我自己的记忆方式是h[r] 包含了“溢出的头部信息”减掉头部剩下的就是你要的区间。2.3 一份可以直接抄的模板我习惯字符串下标从 0 读入但哈希数组从 1 开始存取子串时用闭区间 [l, r]均从 1 编号。C 代码如下#include bits/stdc.h using namespace std; typedef unsigned long long ull; const int MAXN 2000005; const ull base 131; ull pw[MAXN], h[MAXN]; void build(const string s) { int n (int)s.size(); pw[0] 1; for (int i 1; i n; i) pw[i] pw[i - 1] * base; h[0] 0; for (int i 1; i n; i) { h[i] h[i - 1] * base (s[i - 1] - a 1); } } ull get(int l, int r) { // 闭区间 [l, r]1-indexed return h[r] - h[l - 1] * pw[r - l 1]; }这里用的 unsigned long long 是自然溢出相当于自动取模 2^64速度比手动取模快很多。注意 h[i] 的递推里没有写取模正是因为无符号溢出在 C 里的行为是定义好的。如果你不放心也可以把这个模板改成 long long 手动取模的版本后面讲参数时会给出双哈希版本。3. 碰撞概率与参数选择为什么我最终改成了双哈希3.1 生日悖论是哈希的隐形对手单哈希不够稳不是某个字符串单独算错的概率高而是大量比较之后任意一对撞上就可能影响答案。这就像在一个教室里问“有没有两个人同一天生日”23 个人时概率已经超过一半。通用近似公式是当你有 n 个随机取值于 [0, M) 的数两两相撞的概率大约是 1 - exp(-n^2 / (2M))。把 M1e97 代入当比较次数 n 到 5 万左右公式的指数项就是 5e4^2 / (2e9) ≈ 1.25碰撞概率已经不小了。竞赛题里一次排序、一组匹配很容易产生几十万次哈希比较所以单模数 1e97 并不像直觉上那么安全。这个点很多人会忽略直到某道题数据被特别构造过才翻车。3.2 模数、进制该怎么选模数要选质数原因在于质数能避免很多非等价映射如果模数有因子不同字符串的差值在取模时更容易被“吞掉”。常用模数有 1e97、1e99、998244353后面这个是模意义下 NTT 的常用质数当哈希模数也完全没问题。两个 1e9 级别的模数相乘时中间结果不超过 1e18不会溢出 long long 的上限约 9.2e18。进制 base 要大于字符集大小且与模数互质竞赛里最常用的 131、13331 都是基于这个原因。最好不要用 10、26 这种过于小的数字否则字符串的组合规律容易让哈希分布不均匀。还有一个禁忌base 不能取 1否则所有字符串都会退化成同一个前缀和base 也不能取模数的倍数否则第一次插入的字符值全部变成 0哈希立刻失真。3.3 双哈希是对抗碰撞最实用的方案双哈希的思路很直接用两对不同的base, MOD算两套哈希比较时两个整数都相同才算相同。两个模数都取 1e9 级别时相当于在一个约 1e18 的大模数下做哈希安全比较次数提升到千万级别对绝大多数题目的数据量绰绰有余。代价是两倍存储、两倍常数不过哈希本身已经足够便宜退化一点完全在接受范围内。封装成结构体后使用上的差别只是把 get() 返回 pair。这里给出一个双模数版本的实现struct DoubleHash { static const long long M1 1000000007, M2 1000000009; static const long long base 13331; long long h1[MAXN], pw1[MAXN], h2[MAXN], pw2[MAXN]; void build(const string s, int n) { pw1[0] pw2[0] 1; for (int i 1; i n; i) { pw1[i] pw1[i - 1] * base % M1; pw2[i] pw2[i - 1] * base % M2; } for (int i 1; i n; i) { long long v s[i - 1] - a 1; h1[i] (h1[i - 1] * base v) % M1; h2[i] (h2[i - 1] * base v) % M2; } } pairlong long, long long get(int l, int r) { long long a (h1[r] - h1[l - 1] * pw1[r - l 1] % M1 M1) % M1; long long b (h2[r] - h2[l - 1] * pw2[r - l 1] % M2 M2) % M2; return make_pair(a, b); } };3.4 随机 base 是值得养成的习惯就算上了双哈希如果 base 固定理论上出题人仍可以构造碰撞数据更常见的风险是某些数据生成器会让固定 base 的哈希值集中在特定集合。我现在会在程序开始时用随机数种子生成 base取一个 1e9 到 2e9 之间的奇数。这样对方无法提前知道参数针对性构造的成本就高了很多。当然随机化不是万能的。如果题目要求答案严格确定、程序需要反复提交且结果必须稳定那就不要用随机 base或者随机一次后在本地固定下来。我自己往往随机一次 base 后把值打出来确认没问题再拿去跑样例这样兼顾了防护和可复现性。4. 字符串哈希的四个高频应用从原理推一遍4.1 任意子串相等判定这是最基础的一步给定两个区间 [l1, r1]、[l2, r2]且长度相同直接比较 get(l1, r1) 和 get(l2, r2) 即可。长度不同不能直接比因为不同长度的字符串数值上可能恰好相同比较没有意义。这里要特别提醒长度相同是前提忘了这个前提会导致一系列隐蔽的错误。我见过有人先比较两个哈希值相等就算通过却完全没有检查长度。比如判断“某子串是不是另一个的循环节”这类题长度不一致时哈希相等答案就错了。正确做法是把长度检查写在前面或者在 get() 外面包一层带长度的比较函数。4.2 最长公共前缀 LCP 与二分思想如果要计算两个后缀开头位置的 LCP可以对长度做二分若长度为 mid 的两段哈希相等说明前 mid 位相同答案至少是 mid继续向右否则答案比 mid 小向左缩。每次判断 O(1)整个二分 O(log n)。这个套路经常和排序结合对字符串的所有后缀按字典序排序时比较两个后缀可以先取 LCP然后比较 LCP 后一位的字符。有了 O(log n) 的比较函数再用 sort 就是 O(n log^2 n)。它远不如后缀数组 O(n log n) 优但胜在实现简单、几乎不会写错适合比赛时间紧张或者对后缀数组不熟练时使用。我在本地模板里始终保留这个做法很多时候它能救急。4.3 回文半径与正反哈希判断子串 [l, r] 是否为回文可以预处理原串和反转串的哈希。关键点是字符串翻转后原区间 [l, r] 对应反转串里的位置是 [n-r1, n-l1]。两个哈希相等则该区间就是回文。“枚举中心 二分半径”是经典做法。奇数长度回文和偶数长度回文要分开处理枚举中心位置 i二分最大半径 len使得 [i-len, ilen]奇数或 [i-len1, ilen]偶数的哈希满足回文条件。边界条件容易出错我的建议是先在纸上把中心写出来再决定下标偏移不要边写边调。配合正反两个哈希数组这套做法可以稳定处理最长回文子串以及“每个位置作为中心的回文半径”一类问题。4.4 定长模式匹配、子串去重与排序定长模式匹配先算模式串的哈希值再在原串上维护长度为 m 的滑动窗口。实现上可以直接每次调用 get() 查询窗口哈希因为 get() 只做乘法、减法、取模三次操作开销比手工维护窗口还要小而且不容易出现边界 bug。子串去重、计数类题目常用哈希做键把每个子串的哈希值存进 set 或 map。这里必须警惕两件事一是只看单哈希容易被卡二是 unordered_map 的键哈希可能被定向攻击。稳妥做法是把双哈希的 pair 作为键或者干脆用“排序 去重”的方式处理。排序去重有一个天然的好处即使一对字符串真的碰撞了只要双哈希参数合理它们被错误合并的概率几乎为零。千万不要因为贪快就用单哈希 unordered_map省下来的时间可能不够你排查随机 WA。5. 赛后复盘那些哈希比较踩过的坑5.1 负余数是最常见的隐蔽 Bug手动取模的写法里h[r] - h[l-1] * pw[...] % M的结果可能是负数直接取模后还是负数后面无论是比较还是继续参与运算都会出错。我当时在某道题里用if (hash1 hash2)判断发现怎么都对不上最后打印中间值才发现负数已经混进去了。正确的写法是(a % M M) % M虽然啰嗦但能从源头上消灭负数。我建议在模板里固定住这个写法不要每次手敲手敲容易漏。5.2 字符映射从 0 开始会让 “a” 和 “aa” 撞车如果字符串只有小写字母常见的映射s[i] - a会把 a 映射成 0。这时字符串 a 的哈希是 0aa 的哈希也是 0aaa 还是 0因为每读进一个值为 0 的字符相当于给数字乘 base 再加 0结果一直停留在 0。这是一个很容易被忽视的退化场景正确做法是s[i] - a 1或者直接用字符的 ASCII 码。关键原则只有一个任何字符的映射值都不能是 0。5.3 下标习惯不同get() 边界写错哈希数组从 1 开始而字符串下标从 0 开始很容易在调用 get(l, r) 时搞混。我的统一规则是读入字符串 s 后build 时用 s[i - 1]所有查询都传 1-indexed 闭区间。写题时先在注释里写明这个约定然后所有调用都走同一个约定。如果某个题想改成下标从 0 开始必须把 build() 和 get() 一起改单独在调用处改必错。我自己踩过一次改了调用处的参数结果 build 没变查了半小时才发现两个函数的下标体系不一致。5.4 哈希配合二分时的复杂度陷阱二分出长度 mid 后如果每次把整个子串拷贝出来再算哈希复杂度立刻变成 O(mid)整个 LCP 查询变成 O(n log n)数据一大就炸。正确做法永远是用 get() 完成 O(1) 判断。还有一个容易忽略的地方二分边界写不好会导致死循环或越界。我建议直接用标准的while (L R)写法把所有判断条件和偏移都统一成闭区间版本这样不容易出错。5.5 自然溢出与手动取模不要混用如果你用 ull 自然溢出算了一套哈希又用 long long 手动取模算第二套哈希注意两者减法规则完全不同自然溢出的减法不需要额外加 MOD无符号整数的溢出行为是定义好的手动取模必须加 M 再取模。混在一起时最容易出现诡异差异小样例全对大数据随机出错。很多人把两套代码拼一起后忘了这一点排查起来相当痛苦。建议一个项目里只保留一种风格或者把两套封装成独立结构体永远不混用。6. 我现在的取舍习惯写到这里说点个人的经验。字符串哈希不是密码学哈希它不是绝对安全的碰撞只是概率问题但在竞赛环境中只要参数选择合理它的出错概率低到可以忽略而带来的编码效率和速度优势非常大。我现在基本默认双哈希加随机 base除非题目数据量极小否则不冒险用单哈希。如果时间特别紧又不想开双哈希退而求其次的方案是用一个 1e9 质数加随机 base。实测下来单哈希在部分题目上的风险主要集中在“刻意构造的数据”上随机 base 正好把这个漏洞封住。至于自然溢出加固定 base 这种组合我在自己的代码库里已经很少用了不是因为不能跑而是因为已知的碰撞构造方法可以让它稳定出错不值得拿整场比赛去赌。我个人的另一个习惯是把 build() 和 get() 当作工具函数固定在本地模板里平时根本不用重新写。真正需要动脑的永远是题目解法而不是哈希本身。再回头想那场模拟赛如果有人问“哈希会不会撞”我现在会直接告诉他在双哈希和随机 base 的前提下你的算法出错的概率比你程序里一个野指针触发事故的概率还低可以放心用。
阅读完成 · 觉得有帮助？
