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进制数需要对一个模数取余。模数必须足够大以减少不同字符串映射到同一个哈希值的概率即哈希冲突。同时为了计算效率我们通常选择一个大质数或者利用Cunsigned 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[l1]*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-l1}。这样h[l-1] * p[r-l1]就变成了(s[1]*base^{r-1} s[2]*base^{r-2} ... s[l-1]*base^{r-l1})。现在用h[r]减去这个对齐后的值h[r] - h[l-1] * p[r-l1] (s[l]*base^{r-l} ... s[r]*base^{0})这正是我们想要的子串哈希值考虑到取模运算最终的公式为hash(s[l...r]) (h[r] - h[l-1] * p[r-l1] % 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-l1] // 利用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; }关键代码行解析typedef unsigned long long ULL; 这是自然溢出法的关键。ULL的范围是0到2^64-1当乘法或加法结果超过这个范围时会发生环绕wrap-around即自动对2^64取模。这省去了显式取模运算速度更快。h[i] h[i - 1] * base s[i]; 这是构建前缀哈希的核心。h[i-1] * base相当于将前i-1个字符的哈希值这个“K进制数”整体左移一位高位然后加上当前字符s[i]作为新的最低位。return h[r] - h[l - 1] * p[r - l 1]; 这是提取子串哈希值的灵魂。h[l-1] * p[r-l1]将前缀s[1..l-1]的哈希值提升到与s[1..r]中对应部分相同的“数量级”即K进制下的相同高位相减之后高位抵消剩下的就是纯粹的子串s[l..r]的哈希值。由于是ULL运算减法若为负会自然溢出成正数效果等同于(h[r] - h[l-1]*p[r-l1] % MOD MOD) % MOD。实操心得 很多新手在这里会困惑为什么是p[r-l1]而不是p[r-l]。记住一个技巧区间的长度是len r - l 1。我们需要将h[l-1]乘以base^len才能让它“追上”h[r]中对应部分的位置。把这个长度记牢公式就不会错了。4. 经典例题实战解决重复子串问题理论讲得再多不如实战一把。我们来看一个经典问题“最长重复子串”。给定一个字符串找到其中最长的、至少出现两次的连续子串。如果没有返回0。问题分析 暴力枚举所有子串并两两比较复杂度是O(n^4)不可行。字符串哈希给我们提供了快速比较子串的能力。一个常见的思路是二分答案 哈希。思路答案最长长度具有单调性如果长度为L的子串可以重复出现那么长度小于L的子串也一定可以取它的前缀即可。因此我们可以二分查找这个长度L。在二分检查函数check(len)中我们遍历字符串所有长度为len的子串计算它们的哈希值并存入一个哈希表如C的unordered_set或unordered_map。如果在遍历过程中发现某个哈希值已经存在于集合中说明我们找到了一个重复出现的、长度为len的子串函数返回true。如果遍历完都没找到重复则返回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_setULL 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的子串哈希值相同我们误以为找到了重复。在算法竞赛中如果担心被卡有几种策略使用双哈希用两个不同的base和mod或自然溢出分别计算哈希值只有当两个哈希值都相等时才认为子串相等。这能将冲突概率降到极低。在哈希值冲突时进行二次验证当发现哈希值重复时并不立即返回true而是记录下位置最后再对这些候选位置进行直接的字符串比较strcmp。因为冲突通常很少所以实际开销不大。5. 字符串哈希的进阶应用与变形掌握了基础模板和二分哈希的思路我们可以解决一大类字符串问题。下面再介绍几个典型应用场景。5.1 判断回文子串传统判断回文需要O(n)时间。结合哈希我们可以预处理原串和反串的哈希数组然后对于任意子串s[l..r]我们可以O(1)得到它和它的反转串的哈希值并进行比较。这常用于需要多次查询子串是否回文的场景。思路预处理原字符串s的前缀哈希数组h1[]。预处理反转字符串s’的前缀哈希数组h2[]。对于查询[l, r]原串子串哈希为get_hash(h1, l, r)。其在反串中的对应位置是[n-r1, n-l1]哈希值为get_hash(h2, n-r1, n-l1)。比较两者是否相等。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包含两个哈希值 pairLL, LL get_hash(int l, int r) { LL hash1 (h1[r] - h1[l-1] * p1[r-l1] % mod1 mod1) % mod1; LL hash2 (h2[r] - h2[l-1] * p2[r-l1] % 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而该测试点字符串很长且查询很多就很可能是哈希冲突。解决方案换用更强的哈希参数 尝试更换base值例如使用1313131或19260817等更大的质数。有时出题人只针对常见的131和13331。使用双哈希 如上文所示这是最根本的解决方法。几乎可以杜绝竞赛中的数据攻击。使用三哈希或组合哈希 在极端情况下如对安全性要求极高的系统可以使用更多组哈希。但在竞赛中双哈希足矣。6.2 初始化与下标处理易错点下标从1开始 模板中为了公式简洁通常让字符串下标从1开始。scanf(“%s”, s 1)是实现这一点的常用方法。务必注意此时strlen(s)不能用了因为s是char*类型s和s1地址不同。正确获取长度应用strlen(s 1)或用一个变量在读取时记录。p[0]和h[0]的初始化p[0] 1和h[0] 0必须正确设置。p[0]1是因为任何数的0次方为1。h[0]0代表空串哈希值为0。区间边界判断 在get_hash(l, r)函数中务必确保调用时1 l r n。在循环中子串结束位置j i len - 1要判断j n。6.3 性能优化与小技巧使用unsigned long long自然溢出 这比显式取模%运算要快得多是竞赛中的首选。担心冲突就用双哈希。预处理幂数组p 在初始化时一次性计算好p[]数组避免在每次调用get_hash时重复计算base的幂。减少函数调用开销 如果追求极致性能可以将get_hash函数写成宏或内联函数。对于双哈希可以写一个返回pair的函数但多次调用可能有一定开销在超高频查询时可以考虑分别计算两个哈希值。空间换时间h和p数组通常开成全局变量大小根据题目数据范围设定如N1e610。避免在函数内开大数组导致栈溢出。6.4 字符串哈希 vs 其他字符串算法字符串哈希常被拿来与KMP、后缀数组等算法比较。vs KMP KMP用于单模版串匹配问题找一个模式串在文本串中的所有出现位置是O(nm)的比哈希更“标准”。哈希的优势在于可以O(1)比较任意两个子串是否相等功能更通用比如解决“最长重复子串”、“回文子串查询”等问题更方便。vs 后缀数组 后缀数组是字符串处理的“重型武器”能解决几乎所有后缀相关的问题如不同子串个数、最长公共前缀等功能比哈希强大但原理和实现也复杂得多。字符串哈希实现简单在解决特定子串比较问题上代码短、易调试是竞赛中的一把“快刀”。选择建议 如果问题核心是快速比较任意两个子串是否相等或者需要二分答案结合子串比较字符串哈希通常是首选。如果是标准的字符串匹配问题KMP更合适。如果需要处理非常复杂的后缀结构问题则学习后缀数组。我个人在刷题和比赛时字符串哈希是我最常备的工具之一。它的简洁和高效让我在面对字符串问题时总能多一个清晰的思路。记住模板理解原理然后大胆地去应用和变形你会发现很多看似困难的字符串问题都迎刃而解了。最后再强调一遍在关键比赛中如果对安全性有疑虑双哈希是你的不二之选。
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进制数需要对一个模数取余。模数必须足够大以减少不同字符串映射到同一个哈希值的概率即哈希冲突。同时为了计算效率我们通常选择一个大质数或者利用Cunsigned 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[l1]*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-l1}。这样h[l-1] * p[r-l1]就变成了(s[1]*base^{r-1} s[2]*base^{r-2} ... s[l-1]*base^{r-l1})。现在用h[r]减去这个对齐后的值h[r] - h[l-1] * p[r-l1] (s[l]*base^{r-l} ... s[r]*base^{0})这正是我们想要的子串哈希值考虑到取模运算最终的公式为hash(s[l...r]) (h[r] - h[l-1] * p[r-l1] % 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-l1] // 利用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; }关键代码行解析typedef unsigned long long ULL; 这是自然溢出法的关键。ULL的范围是0到2^64-1当乘法或加法结果超过这个范围时会发生环绕wrap-around即自动对2^64取模。这省去了显式取模运算速度更快。h[i] h[i - 1] * base s[i]; 这是构建前缀哈希的核心。h[i-1] * base相当于将前i-1个字符的哈希值这个“K进制数”整体左移一位高位然后加上当前字符s[i]作为新的最低位。return h[r] - h[l - 1] * p[r - l 1]; 这是提取子串哈希值的灵魂。h[l-1] * p[r-l1]将前缀s[1..l-1]的哈希值提升到与s[1..r]中对应部分相同的“数量级”即K进制下的相同高位相减之后高位抵消剩下的就是纯粹的子串s[l..r]的哈希值。由于是ULL运算减法若为负会自然溢出成正数效果等同于(h[r] - h[l-1]*p[r-l1] % MOD MOD) % MOD。实操心得 很多新手在这里会困惑为什么是p[r-l1]而不是p[r-l]。记住一个技巧区间的长度是len r - l 1。我们需要将h[l-1]乘以base^len才能让它“追上”h[r]中对应部分的位置。把这个长度记牢公式就不会错了。4. 经典例题实战解决重复子串问题理论讲得再多不如实战一把。我们来看一个经典问题“最长重复子串”。给定一个字符串找到其中最长的、至少出现两次的连续子串。如果没有返回0。问题分析 暴力枚举所有子串并两两比较复杂度是O(n^4)不可行。字符串哈希给我们提供了快速比较子串的能力。一个常见的思路是二分答案 哈希。思路答案最长长度具有单调性如果长度为L的子串可以重复出现那么长度小于L的子串也一定可以取它的前缀即可。因此我们可以二分查找这个长度L。在二分检查函数check(len)中我们遍历字符串所有长度为len的子串计算它们的哈希值并存入一个哈希表如C的unordered_set或unordered_map。如果在遍历过程中发现某个哈希值已经存在于集合中说明我们找到了一个重复出现的、长度为len的子串函数返回true。如果遍历完都没找到重复则返回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_setULL 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的子串哈希值相同我们误以为找到了重复。在算法竞赛中如果担心被卡有几种策略使用双哈希用两个不同的base和mod或自然溢出分别计算哈希值只有当两个哈希值都相等时才认为子串相等。这能将冲突概率降到极低。在哈希值冲突时进行二次验证当发现哈希值重复时并不立即返回true而是记录下位置最后再对这些候选位置进行直接的字符串比较strcmp。因为冲突通常很少所以实际开销不大。5. 字符串哈希的进阶应用与变形掌握了基础模板和二分哈希的思路我们可以解决一大类字符串问题。下面再介绍几个典型应用场景。5.1 判断回文子串传统判断回文需要O(n)时间。结合哈希我们可以预处理原串和反串的哈希数组然后对于任意子串s[l..r]我们可以O(1)得到它和它的反转串的哈希值并进行比较。这常用于需要多次查询子串是否回文的场景。思路预处理原字符串s的前缀哈希数组h1[]。预处理反转字符串s’的前缀哈希数组h2[]。对于查询[l, r]原串子串哈希为get_hash(h1, l, r)。其在反串中的对应位置是[n-r1, n-l1]哈希值为get_hash(h2, n-r1, n-l1)。比较两者是否相等。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包含两个哈希值 pairLL, LL get_hash(int l, int r) { LL hash1 (h1[r] - h1[l-1] * p1[r-l1] % mod1 mod1) % mod1; LL hash2 (h2[r] - h2[l-1] * p2[r-l1] % 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而该测试点字符串很长且查询很多就很可能是哈希冲突。解决方案换用更强的哈希参数 尝试更换base值例如使用1313131或19260817等更大的质数。有时出题人只针对常见的131和13331。使用双哈希 如上文所示这是最根本的解决方法。几乎可以杜绝竞赛中的数据攻击。使用三哈希或组合哈希 在极端情况下如对安全性要求极高的系统可以使用更多组哈希。但在竞赛中双哈希足矣。6.2 初始化与下标处理易错点下标从1开始 模板中为了公式简洁通常让字符串下标从1开始。scanf(“%s”, s 1)是实现这一点的常用方法。务必注意此时strlen(s)不能用了因为s是char*类型s和s1地址不同。正确获取长度应用strlen(s 1)或用一个变量在读取时记录。p[0]和h[0]的初始化p[0] 1和h[0] 0必须正确设置。p[0]1是因为任何数的0次方为1。h[0]0代表空串哈希值为0。区间边界判断 在get_hash(l, r)函数中务必确保调用时1 l r n。在循环中子串结束位置j i len - 1要判断j n。6.3 性能优化与小技巧使用unsigned long long自然溢出 这比显式取模%运算要快得多是竞赛中的首选。担心冲突就用双哈希。预处理幂数组p 在初始化时一次性计算好p[]数组避免在每次调用get_hash时重复计算base的幂。减少函数调用开销 如果追求极致性能可以将get_hash函数写成宏或内联函数。对于双哈希可以写一个返回pair的函数但多次调用可能有一定开销在超高频查询时可以考虑分别计算两个哈希值。空间换时间h和p数组通常开成全局变量大小根据题目数据范围设定如N1e610。避免在函数内开大数组导致栈溢出。6.4 字符串哈希 vs 其他字符串算法字符串哈希常被拿来与KMP、后缀数组等算法比较。vs KMP KMP用于单模版串匹配问题找一个模式串在文本串中的所有出现位置是O(nm)的比哈希更“标准”。哈希的优势在于可以O(1)比较任意两个子串是否相等功能更通用比如解决“最长重复子串”、“回文子串查询”等问题更方便。vs 后缀数组 后缀数组是字符串处理的“重型武器”能解决几乎所有后缀相关的问题如不同子串个数、最长公共前缀等功能比哈希强大但原理和实现也复杂得多。字符串哈希实现简单在解决特定子串比较问题上代码短、易调试是竞赛中的一把“快刀”。选择建议 如果问题核心是快速比较任意两个子串是否相等或者需要二分答案结合子串比较字符串哈希通常是首选。如果是标准的字符串匹配问题KMP更合适。如果需要处理非常复杂的后缀结构问题则学习后缀数组。我个人在刷题和比赛时字符串哈希是我最常备的工具之一。它的简洁和高效让我在面对字符串问题时总能多一个清晰的思路。记住模板理解原理然后大胆地去应用和变形你会发现很多看似困难的字符串问题都迎刃而解了。最后再强调一遍在关键比赛中如果对安全性有疑虑双哈希是你的不二之选。
