在算法竞赛的征途上字符串处理是每一位选手都无法绕开的基石。无论是处理用户输入、解析复杂数据还是解决核心的字符串匹配、查找问题扎实的字符串算法功底往往能决定比赛的走向。今天我们聚焦于西安交通大学ACM算法竞赛小学期课程第九天的核心内容——字符串专题深入剖析哈希Hash与KMPKnuth-Morris-Pratt这两大“神兵利器”。本文将带你从零理解其原理手把手实现代码并通过经典例题巩固所学目标是让你在下次遇到字符串问题时能够游刃有余地选择并应用合适的算法。1. 字符串算法在ACM竞赛中的核心地位在ACM国际大学生程序设计竞赛ICPC及各类在线评测平台如Codeforces、LeetCode中字符串相关题目出现频率极高。它们不仅考察选手对基础数据结构的掌握更考验将抽象问题转化为高效算法模型的能力。字符串问题的典型场景包括但不限于精确匹配在一个文本串Text中快速查找一个模式串Pattern的所有出现位置。这是最经典的问题KMP算法正是为此而生。子串查找与统计查询一个字符串中某段子串是否出现、出现次数或者比较两个子串是否相同。朴素遍历比较的O(N*M)复杂度在数据量大时不可接受字符串哈希提供了近乎O(1)的快速比较方案。回文串相关判断回文串、寻找最长回文子串等常使用哈希或专门的Manacher算法。字典序比较与排序涉及字符串的排序、最大最小表示等问题。面对这些场景暴力枚举Brute-Force算法虽然直观但其时间复杂度往往高达O(N*M)无法通过大数据量的测试。因此掌握像字符串哈希和KMP这样的高效算法是从“算法小白”迈向“竞赛选手”的关键一步。2. 环境准备与代码规范在开始算法学习之前确保你的编程环境已就绪并了解竞赛中的通用代码框架。编程语言与环境语言C 是ACM竞赛的绝对主流因其运行速度快、STL库强大。本文所有示例代码将使用C编写。编译器推荐使用GCCG或Clang确保支持C11及以上标准。开发环境可以选择轻量级的代码编辑器如VS Code、Sublime Text配合命令行或者使用集成的IDE如Code::Blocks, Dev-C 或者Clion。ACM模式输入输出 与力扣LeetCode的核心代码模式不同ACM竞赛要求选手处理完整的输入输出。以下是标准做法#include iostream #include string using namespace std; int main() { // 示例读取未知数量的字符串直到文件结束 string s; while (cin s) { // 或 while(getline(cin, s)) 用于读取整行 // 处理字符串 s // ... // 输出结果 cout result endl; } return 0; }关键点使用while(cin var)来循环读取直到输入流结束EOF这是应对多组测试数据的通用写法。头文件与命名空间 字符串算法常用到头文件#include iostream // 输入输出 #include string // C string 类 #include vector // 动态数组 #include algorithm // 算法函数如sort using namespace std; // 简化代码竞赛中常用3. 字符串哈希String Hashing详解字符串哈希的核心思想是将一个字符串映射成一个整数哈希值从而使得字符串的比较转化为整数的比较将时间复杂度从O(N)降低到O(1)。3.1 哈希函数与原理我们采用最常见的“多项式滚动哈希”。将一个字符串看作一个P进制的数然后对一个较大的数M取模得到哈希值。对于一个字符串s s[0]s[1]...s[n-1]其哈希值hash(s)定义为hash(s) (s[0] * P^(n-1) s[1] * P^(n-2) ... s[n-1] * P^0) mod M其中P是一个自选的进制基数通常取一个质数如131, 13331等。M是取模的大数为了减少哈希冲突通常取一个很大的质数如2^64利用unsigned long long自然溢出、1e97或998244353。前缀哈希数组 为了快速计算任意子串的哈希值我们预先计算字符串每个前缀的哈希值存储到数组h中。 定义h[i]为字符串s前i个字符的哈希值即s[0...i-1]。 递推公式h[i] (h[i-1] * P s[i-1]) % M同时我们还需要预处理进制权值数组p其中p[i] P^i % M。3.2 子串哈希值计算有了前缀哈希数组h和权值数组p我们可以用O(1)时间计算出子串s[l...r]下标从0开始闭区间的哈希值hash(s[l...r]) (h[r1] - h[l] * p[r-l1] % M M) % M公式解释h[r1]对应s[0...r]。h[l]对应s[0...l-1]。h[l] * p[r-l1]相当于将前缀s[0...l-1]左移到与h[r1]对齐的位置两者相减就得到了s[l...r]的哈希值。加M再取模是为了防止出现负数。3.3 代码实现与示例下面是一个完整的双哈希使用两个模数以减少冲突概率实现示例#include iostream #include string #include vector using namespace std; typedef unsigned long long ULL; class StringHash { public: string s; int n; ULL P 131; // 进制基数 vectorULL h; // 前缀哈希数组 vectorULL p; // 权值数组 StringHash(const string str) : s(str), n(str.size()) { h.resize(n 1, 0); p.resize(n 1, 1); for (int i 1; i n; i) { p[i] p[i - 1] * P; // 自然溢出相当于 mod 2^64 h[i] h[i - 1] * P s[i - 1]; // 计算前缀哈希 } } // 获取子串 s[l...r] 的哈希值 (下标从0开始) ULL getHash(int l, int r) { if (l 0 || r n || l r) return 0; return h[r 1] - h[l] * p[r - l 1]; } }; int main() { string text ababcabc; StringHash sh(text); // 示例比较子串 abc 在文本中出现的位置 string pattern abc; StringHash ph(pattern); ULL targetHash ph.getHash(0, pattern.size() - 1); cout 在文本 \ text \ 中查找子串 \ pattern \: endl; for (int i 0; i text.size() - pattern.size(); i) { if (sh.getHash(i, i pattern.size() - 1) targetHash) { // 严谨情况下哈希相等后应进行逐字符验证防止哈希冲突 if (text.substr(i, pattern.size()) pattern) { cout 找到匹配起始位置: i endl; } } } return 0; }运行结果在文本 ababcabc 中查找子串 abc: 找到匹配起始位置: 2 找到匹配起始位置: 53.4 哈希的应用场景与优缺点应用场景快速判断两个子串是否相等O(1)时间比较。字符串匹配可以用于实现简化版的字符串匹配但通常不如KMP专精。最长回文子串结合正反哈希可以在O(NlogN)内解决。最长公共前缀(LCP)二分长度哈希检查。优点实现相对简单易于理解。查询速度极快O(1)。灵活性强可用于解决多种衍生问题。缺点存在哈希冲突的风险尽管概率极低。在关键比赛中可以使用双哈希两个不同的P和M来进一步降低冲突概率。是一种概率算法理论上不能保证100%正确但实践中足够可靠。4. KMP算法深度解析KMP算法用于解决经典的单模式串匹配问题给定文本串T和模式串P找出P在T中所有出现的位置。其核心在于当匹配失败时利用已匹配的信息避免文本串指针的回退从而实现O(NM)的线性时间复杂度。4.1 核心概念前缀函数Next数组KMP算法的灵魂是前缀函数通常代码中记为next数组。对于模式串Pnext[i]定义为子串P[0...i]的最长的、相等的真前缀与真后缀的长度。真前缀不包含最后一个字符的前缀。真后缀不包含第一个字符的后缀。例如模式串P ababci0子串a无真前缀/后缀next[0] 0通常实现中设为-1或0下文以0开始为例。i1子串ab真前缀{a}真后缀{b}无相等next[1] 0。i2子串aba真前缀{a,ab}真后缀{ba,a}相等的最长串为a长度1next[2] 1。i3子串abab真前缀{a,ab,aba}真后缀{bab,ab,b}相等的最长串为ab长度2next[3] 2。i4子串ababc真前缀{a,ab,aba,abab}真后缀{babc,abc,bc,c}无相等next[4] 0。next数组的意义在于当在位置i匹配失败时模式串指针j可以直接跳转到next[j-1]的位置继续匹配因为next[j-1]之前的字符已经确保和文本串当前对齐的位置是匹配的。4.2 算法流程与模拟假设文本串T abababcabab模式串P ababc其next [0, 0, 1, 2, 0]。初始化i指向T开头j指向P开头。匹配过程T[0]avsP[0]a匹配i, j。T[1]bvsP[1]b匹配i, j。T[2]avsP[2]a匹配i, j。T[3]bvsP[3]b匹配i, j。T[4]avsP[4]c失配 此时j4查next[j-1] next[3] 2。 将j回退到2。这意味着我们不用比较P[0]和P[1]了因为P[0..1]已经和T[2..3]匹配上了由next数组保证。现在比较T[4]avsP[2]a匹配i, j。T[5]bvsP[3]b匹配i, j。T[6]cvsP[4]c匹配j到达模式串末尾匹配成功记录位置i - j 6 - 5 1实际上匹配起始位置是2这里计算需注意。然后将j置为next[j-1]继续寻找下一个匹配。重复直到文本串遍历完毕。可以看到文本串指针i从未回退一直向前移动这是KMP高效的关键。4.3 代码实现KMP实现分为两部分构建next数组和执行匹配。#include iostream #include string #include vector using namespace std; // 构建模式串P的next数组 (前缀函数) vectorint buildNext(const string P) { int m P.size(); vectorint next(m, 0); // next[0] 必然是0 for (int i 1, j 0; i m; i) { // j 指向前缀末尾i 指向后缀末尾 // 不匹配时j 回退 while (j 0 P[i] ! P[j]) { j next[j - 1]; } // 匹配时j 前进 if (P[i] P[j]) { j; } next[i] j; } return next; } // KMP 主函数返回所有匹配的起始位置 vectorint kmpSearch(const string T, const string P) { vectorint positions; int n T.size(), m P.size(); if (m 0) return positions; // 空模式串 vectorint next buildNext(P); for (int i 0, j 0; i n; i) { // i 遍历文本串j 指向模式串 // 不匹配时j 根据next数组回退 while (j 0 T[i] ! P[j]) { j next[j - 1]; } // 匹配时j 前进 if (T[i] P[j]) { j; } // 找到完整匹配 if (j m) { positions.push_back(i - m 1); // 记录起始下标 j next[j - 1]; // 继续寻找下一个可能匹配 } } return positions; } int main() { string text abababcabababb; string pattern ababc; cout 文本串: \ text \ endl; cout 模式串: \ pattern \ endl; vectorint next buildNext(pattern); cout Next 数组: ; for (int val : next) cout val ; cout endl; vectorint matches kmpSearch(text, pattern); if (matches.empty()) { cout 未找到匹配。 endl; } else { cout 匹配起始位置: ; for (int pos : matches) cout pos ; cout endl; } return 0; }运行结果文本串: abababcabababb 模式串: ababc Next 数组: 0 0 1 2 0 匹配起始位置: 24.4 KMP算法的变体与应用最小循环节对于一个长度为n的字符串s如果n % (n - next[n-1]) 0则字符串可以由长度为n - next[n-1]的子串重复构成该子串即为最小循环节。失配指针的应用next数组本身可以用于解决许多与字符串周期、边界相关的问题。5. 哈希与KMP的对比与选择特性字符串哈希KMP算法主要用途快速比较子串是否相等支持随机访问单模式串精确匹配时间复杂度预处理 O(N)查询 O(1)预处理 O(M)匹配 O(NM)空间复杂度O(N)O(M)优势查询快可解决多种子串比较问题匹配过程稳定无哈希冲突风险理论保证劣势存在极低概率哈希冲突风险只能解决模式匹配功能相对单一选择建议需要频繁比较不同位置子串、解决回文串、LCP等问题时专注于在一个文本中找一个模式串的所有出现时简单来说如果题目核心是“比较”考虑哈希如果核心是“查找所有出现位置”KMP是更标准的选择。6. 综合实战例题演练让我们通过一道融合了哈希和KMP思想的经典题目来巩固理解。题目给定一个字符串s求出其最长回文子串。要求时间复杂度低于 O(N^2)。思路分析 暴力枚举所有子串需要 O(N^2)再判断回文需要 O(N)总复杂度 O(N^3)。我们可以用字符串哈希将判断回文优化到 O(1)。预处理字符串s的正向哈希和反向哈希。枚举回文串的中心点奇长度中心为一个字符偶长度中心为两个字符之间。对于每个中心用二分法查找以其为中心的最长回文半径。二分半径长度len通过比较正向子串哈希和反向子串哈希是否相等来判断该半径下的子串是否为回文。时间复杂度枚举中心 O(N)二分查找 O(logN)哈希比较 O(1)总复杂度 O(N logN)。代码实现#include iostream #include string #include vector #include algorithm using namespace std; typedef unsigned long long ULL; const ULL P 131; class DoubleHash { public: string s; int n; vectorULL h1, h2; // h1: 正向哈希 h2: 反向哈希 vectorULL p; DoubleHash(const string str) : s(str), n(str.size()) { h1.resize(n 1, 0); h2.resize(n 1, 0); p.resize(n 1, 1); // 计算正向哈希 for (int i 1; i n; i) { p[i] p[i - 1] * P; h1[i] h1[i - 1] * P s[i - 1]; } // 计算反向哈希 for (int i 1; i n; i) { h2[i] h2[i - 1] * P s[n - i]; } } // 获取正向子串 s[l...r] 的哈希值 ULL getHash1(int l, int r) { return h1[r 1] - h1[l] * p[r - l 1]; } // 获取反向子串 s[l...r] 的哈希值 (注意坐标转换) ULL getHash2(int l, int r) { // 原串 s[l...r] 在反向串中对应 s[n-1-r ... n-1-l] int rev_l n - 1 - r; int rev_r n - 1 - l; return h2[rev_r 1] - h2[rev_l] * p[rev_r - rev_l 1]; } // 判断子串 s[l...r] 是否是回文 bool isPalindrome(int l, int r) { return getHash1(l, r) getHash2(l, r); } }; string longestPalindrome(string s) { int n s.size(); if (n 1) return s; DoubleHash dh(s); int start 0, maxLen 1; // 枚举中心点 for (int center 0; center n; center) { // 奇数长度回文中心为 center int left 0, right min(center, n - 1 - center); while (left right) { int mid (left right 1) 1; if (dh.isPalindrome(center - mid, center mid)) { left mid; } else { right mid - 1; } } int len 2 * left 1; if (len maxLen) { maxLen len; start center - left; } // 偶数长度回文中心为 center 和 center1 之间 if (center 1 n s[center] s[center 1]) { left 0; right min(center, n - 2 - center); while (left right) { int mid (left right 1) 1; if (dh.isPalindrome(center - mid, center 1 mid)) { left mid; } else { right mid - 1; } } len 2 * left 2; if (len maxLen) { maxLen len; start center - left; } } } return s.substr(start, maxLen); } int main() { string test1 babad; string test2 cbbd; cout 测试1: \ test1 \ - \ longestPalindrome(test1) \ endl; cout 测试2: \ test2 \ - \ longestPalindrome(test2) \ endl; return 0; }7. 常见问题与调试技巧Q1: 哈希冲突了怎么办A1: 首先确保使用了足够大的质数作为进制P和模数M。最有效的方法是使用双哈希即用两组不同的(P, M)分别计算哈希值只有当两个哈希值都相等时才认为字符串相等。可以将两个哈希值组成一个pairULL, ULL来使用。Q2: KMP的next数组有的版本从-1开始有的从0开始有什么区别A2: 这只是实现上的细节差异核心思想一致。next[0] -1表示当模式串第一个字符就失配时文本串指针i需要后移模式串指针j被重置为-1然后i, j变成0。代码中while循环条件常写为while (j 0 P[i] ! P[j])。next[0] 0如上文实现表示长度为1的子串没有真前缀/后缀。匹配时回退逻辑稍有不同但最终效果等价。选择一种并理解其状态转移即可。Q3: 如何调试KMP算法A3:打印next数组首先验证你计算的next数组是否正确。可以手动计算几个简单字符串的next数组进行比对。模拟单步执行在匹配循环中打印出每一步的i(文本串索引),j(模式串索引),T[i],P[j]的值对照算法流程手动模拟看指针跳转是否符合预期。使用简单测试用例从Taaaaa,Paa这样的简单例子开始测试。Q4: 字符串下标是从0开始还是1开始A4: 在C中string类型下标从0开始。本文所有代码和讲解均使用0-基索引。在构建前缀数组(h,next)时我们通常让h[i]对应原串s[0...i-1]这是为了公式推导和计算的方便。务必在代码中保持逻辑一致否则极易出错。8. 工程实践与最佳建议封装工具类在竞赛或项目中将字符串哈希和KMP算法封装成独立的类或函数模板。这样在主逻辑中只需关注调用提高代码复用性和整洁度。注意数据范围与溢出哈希运算中使用unsigned long long让其自然溢出模2^64是最方便的做法。如果使用固定模数如1e97务必在每次乘法和加法后取模。KMP算法中next数组和匹配循环的索引不要越界。理解优于记忆不要死记硬背next数组的构建代码或哈希公式。花时间理解其背后的状态转移和前缀后缀公共元素的概念这样才能在遇到变种题目时灵活应对。结合其他算法字符串问题常常不是孤立的。哈希可以结合二分答案、滑动窗口KMP的next数组可以用于求解字符串周期。掌握这些组合技巧能解决更复杂的问题。从暴力法出发在思考优化算法前先想清楚暴力解法O(N^2)或O(N^3)怎么做。这能帮你理清问题本质并明确优化方向如何减少重复比较、如何避免指针回退。字符串算法的学习路径可以遵循理解基础概念 - 掌握暴力解法 - 学习经典优化算法哈希、KMP- 练习典型例题 - 探索扩展算法字典树、AC自动机、后缀数组等。将第九天的哈希与KMP真正内化你就为后续更复杂的字符串与文本处理问题打下了坚实的基础。多写代码多模拟多总结在不断的实践中这些精妙的算法思想将成为你解决问题的本能反应。 
长河君 · 2026/9/2 10:48:31 · 阅读 1.2k ACM竞赛必备：字符串哈希与KMP算法原理、实现与应用详解
在算法竞赛的征途上字符串处理是每一位选手都无法绕开的基石。无论是处理用户输入、解析复杂数据还是解决核心的字符串匹配、查找问题扎实的字符串算法功底往往能决定比赛的走向。今天我们聚焦于西安交通大学ACM算法竞赛小学期课程第九天的核心内容——字符串专题深入剖析哈希Hash与KMPKnuth-Morris-Pratt这两大“神兵利器”。本文将带你从零理解其原理手把手实现代码并通过经典例题巩固所学目标是让你在下次遇到字符串问题时能够游刃有余地选择并应用合适的算法。1. 字符串算法在ACM竞赛中的核心地位在ACM国际大学生程序设计竞赛ICPC及各类在线评测平台如Codeforces、LeetCode中字符串相关题目出现频率极高。它们不仅考察选手对基础数据结构的掌握更考验将抽象问题转化为高效算法模型的能力。字符串问题的典型场景包括但不限于精确匹配在一个文本串Text中快速查找一个模式串Pattern的所有出现位置。这是最经典的问题KMP算法正是为此而生。子串查找与统计查询一个字符串中某段子串是否出现、出现次数或者比较两个子串是否相同。朴素遍历比较的O(N*M)复杂度在数据量大时不可接受字符串哈希提供了近乎O(1)的快速比较方案。回文串相关判断回文串、寻找最长回文子串等常使用哈希或专门的Manacher算法。字典序比较与排序涉及字符串的排序、最大最小表示等问题。面对这些场景暴力枚举Brute-Force算法虽然直观但其时间复杂度往往高达O(N*M)无法通过大数据量的测试。因此掌握像字符串哈希和KMP这样的高效算法是从“算法小白”迈向“竞赛选手”的关键一步。2. 环境准备与代码规范在开始算法学习之前确保你的编程环境已就绪并了解竞赛中的通用代码框架。编程语言与环境语言C 是ACM竞赛的绝对主流因其运行速度快、STL库强大。本文所有示例代码将使用C编写。编译器推荐使用GCCG或Clang确保支持C11及以上标准。开发环境可以选择轻量级的代码编辑器如VS Code、Sublime Text配合命令行或者使用集成的IDE如Code::Blocks, Dev-C 或者Clion。ACM模式输入输出 与力扣LeetCode的核心代码模式不同ACM竞赛要求选手处理完整的输入输出。以下是标准做法#include iostream #include string using namespace std; int main() { // 示例读取未知数量的字符串直到文件结束 string s; while (cin s) { // 或 while(getline(cin, s)) 用于读取整行 // 处理字符串 s // ... // 输出结果 cout result endl; } return 0; }关键点使用while(cin var)来循环读取直到输入流结束EOF这是应对多组测试数据的通用写法。头文件与命名空间 字符串算法常用到头文件#include iostream // 输入输出 #include string // C string 类 #include vector // 动态数组 #include algorithm // 算法函数如sort using namespace std; // 简化代码竞赛中常用3. 字符串哈希String Hashing详解字符串哈希的核心思想是将一个字符串映射成一个整数哈希值从而使得字符串的比较转化为整数的比较将时间复杂度从O(N)降低到O(1)。3.1 哈希函数与原理我们采用最常见的“多项式滚动哈希”。将一个字符串看作一个P进制的数然后对一个较大的数M取模得到哈希值。对于一个字符串s s[0]s[1]...s[n-1]其哈希值hash(s)定义为hash(s) (s[0] * P^(n-1) s[1] * P^(n-2) ... s[n-1] * P^0) mod M其中P是一个自选的进制基数通常取一个质数如131, 13331等。M是取模的大数为了减少哈希冲突通常取一个很大的质数如2^64利用unsigned long long自然溢出、1e97或998244353。前缀哈希数组 为了快速计算任意子串的哈希值我们预先计算字符串每个前缀的哈希值存储到数组h中。 定义h[i]为字符串s前i个字符的哈希值即s[0...i-1]。 递推公式h[i] (h[i-1] * P s[i-1]) % M同时我们还需要预处理进制权值数组p其中p[i] P^i % M。3.2 子串哈希值计算有了前缀哈希数组h和权值数组p我们可以用O(1)时间计算出子串s[l...r]下标从0开始闭区间的哈希值hash(s[l...r]) (h[r1] - h[l] * p[r-l1] % M M) % M公式解释h[r1]对应s[0...r]。h[l]对应s[0...l-1]。h[l] * p[r-l1]相当于将前缀s[0...l-1]左移到与h[r1]对齐的位置两者相减就得到了s[l...r]的哈希值。加M再取模是为了防止出现负数。3.3 代码实现与示例下面是一个完整的双哈希使用两个模数以减少冲突概率实现示例#include iostream #include string #include vector using namespace std; typedef unsigned long long ULL; class StringHash { public: string s; int n; ULL P 131; // 进制基数 vectorULL h; // 前缀哈希数组 vectorULL p; // 权值数组 StringHash(const string str) : s(str), n(str.size()) { h.resize(n 1, 0); p.resize(n 1, 1); for (int i 1; i n; i) { p[i] p[i - 1] * P; // 自然溢出相当于 mod 2^64 h[i] h[i - 1] * P s[i - 1]; // 计算前缀哈希 } } // 获取子串 s[l...r] 的哈希值 (下标从0开始) ULL getHash(int l, int r) { if (l 0 || r n || l r) return 0; return h[r 1] - h[l] * p[r - l 1]; } }; int main() { string text ababcabc; StringHash sh(text); // 示例比较子串 abc 在文本中出现的位置 string pattern abc; StringHash ph(pattern); ULL targetHash ph.getHash(0, pattern.size() - 1); cout 在文本 \ text \ 中查找子串 \ pattern \: endl; for (int i 0; i text.size() - pattern.size(); i) { if (sh.getHash(i, i pattern.size() - 1) targetHash) { // 严谨情况下哈希相等后应进行逐字符验证防止哈希冲突 if (text.substr(i, pattern.size()) pattern) { cout 找到匹配起始位置: i endl; } } } return 0; }运行结果在文本 ababcabc 中查找子串 abc: 找到匹配起始位置: 2 找到匹配起始位置: 53.4 哈希的应用场景与优缺点应用场景快速判断两个子串是否相等O(1)时间比较。字符串匹配可以用于实现简化版的字符串匹配但通常不如KMP专精。最长回文子串结合正反哈希可以在O(NlogN)内解决。最长公共前缀(LCP)二分长度哈希检查。优点实现相对简单易于理解。查询速度极快O(1)。灵活性强可用于解决多种衍生问题。缺点存在哈希冲突的风险尽管概率极低。在关键比赛中可以使用双哈希两个不同的P和M来进一步降低冲突概率。是一种概率算法理论上不能保证100%正确但实践中足够可靠。4. KMP算法深度解析KMP算法用于解决经典的单模式串匹配问题给定文本串T和模式串P找出P在T中所有出现的位置。其核心在于当匹配失败时利用已匹配的信息避免文本串指针的回退从而实现O(NM)的线性时间复杂度。4.1 核心概念前缀函数Next数组KMP算法的灵魂是前缀函数通常代码中记为next数组。对于模式串Pnext[i]定义为子串P[0...i]的最长的、相等的真前缀与真后缀的长度。真前缀不包含最后一个字符的前缀。真后缀不包含第一个字符的后缀。例如模式串P ababci0子串a无真前缀/后缀next[0] 0通常实现中设为-1或0下文以0开始为例。i1子串ab真前缀{a}真后缀{b}无相等next[1] 0。i2子串aba真前缀{a,ab}真后缀{ba,a}相等的最长串为a长度1next[2] 1。i3子串abab真前缀{a,ab,aba}真后缀{bab,ab,b}相等的最长串为ab长度2next[3] 2。i4子串ababc真前缀{a,ab,aba,abab}真后缀{babc,abc,bc,c}无相等next[4] 0。next数组的意义在于当在位置i匹配失败时模式串指针j可以直接跳转到next[j-1]的位置继续匹配因为next[j-1]之前的字符已经确保和文本串当前对齐的位置是匹配的。4.2 算法流程与模拟假设文本串T abababcabab模式串P ababc其next [0, 0, 1, 2, 0]。初始化i指向T开头j指向P开头。匹配过程T[0]avsP[0]a匹配i, j。T[1]bvsP[1]b匹配i, j。T[2]avsP[2]a匹配i, j。T[3]bvsP[3]b匹配i, j。T[4]avsP[4]c失配 此时j4查next[j-1] next[3] 2。 将j回退到2。这意味着我们不用比较P[0]和P[1]了因为P[0..1]已经和T[2..3]匹配上了由next数组保证。现在比较T[4]avsP[2]a匹配i, j。T[5]bvsP[3]b匹配i, j。T[6]cvsP[4]c匹配j到达模式串末尾匹配成功记录位置i - j 6 - 5 1实际上匹配起始位置是2这里计算需注意。然后将j置为next[j-1]继续寻找下一个匹配。重复直到文本串遍历完毕。可以看到文本串指针i从未回退一直向前移动这是KMP高效的关键。4.3 代码实现KMP实现分为两部分构建next数组和执行匹配。#include iostream #include string #include vector using namespace std; // 构建模式串P的next数组 (前缀函数) vectorint buildNext(const string P) { int m P.size(); vectorint next(m, 0); // next[0] 必然是0 for (int i 1, j 0; i m; i) { // j 指向前缀末尾i 指向后缀末尾 // 不匹配时j 回退 while (j 0 P[i] ! P[j]) { j next[j - 1]; } // 匹配时j 前进 if (P[i] P[j]) { j; } next[i] j; } return next; } // KMP 主函数返回所有匹配的起始位置 vectorint kmpSearch(const string T, const string P) { vectorint positions; int n T.size(), m P.size(); if (m 0) return positions; // 空模式串 vectorint next buildNext(P); for (int i 0, j 0; i n; i) { // i 遍历文本串j 指向模式串 // 不匹配时j 根据next数组回退 while (j 0 T[i] ! P[j]) { j next[j - 1]; } // 匹配时j 前进 if (T[i] P[j]) { j; } // 找到完整匹配 if (j m) { positions.push_back(i - m 1); // 记录起始下标 j next[j - 1]; // 继续寻找下一个可能匹配 } } return positions; } int main() { string text abababcabababb; string pattern ababc; cout 文本串: \ text \ endl; cout 模式串: \ pattern \ endl; vectorint next buildNext(pattern); cout Next 数组: ; for (int val : next) cout val ; cout endl; vectorint matches kmpSearch(text, pattern); if (matches.empty()) { cout 未找到匹配。 endl; } else { cout 匹配起始位置: ; for (int pos : matches) cout pos ; cout endl; } return 0; }运行结果文本串: abababcabababb 模式串: ababc Next 数组: 0 0 1 2 0 匹配起始位置: 24.4 KMP算法的变体与应用最小循环节对于一个长度为n的字符串s如果n % (n - next[n-1]) 0则字符串可以由长度为n - next[n-1]的子串重复构成该子串即为最小循环节。失配指针的应用next数组本身可以用于解决许多与字符串周期、边界相关的问题。5. 哈希与KMP的对比与选择特性字符串哈希KMP算法主要用途快速比较子串是否相等支持随机访问单模式串精确匹配时间复杂度预处理 O(N)查询 O(1)预处理 O(M)匹配 O(NM)空间复杂度O(N)O(M)优势查询快可解决多种子串比较问题匹配过程稳定无哈希冲突风险理论保证劣势存在极低概率哈希冲突风险只能解决模式匹配功能相对单一选择建议需要频繁比较不同位置子串、解决回文串、LCP等问题时专注于在一个文本中找一个模式串的所有出现时简单来说如果题目核心是“比较”考虑哈希如果核心是“查找所有出现位置”KMP是更标准的选择。6. 综合实战例题演练让我们通过一道融合了哈希和KMP思想的经典题目来巩固理解。题目给定一个字符串s求出其最长回文子串。要求时间复杂度低于 O(N^2)。思路分析 暴力枚举所有子串需要 O(N^2)再判断回文需要 O(N)总复杂度 O(N^3)。我们可以用字符串哈希将判断回文优化到 O(1)。预处理字符串s的正向哈希和反向哈希。枚举回文串的中心点奇长度中心为一个字符偶长度中心为两个字符之间。对于每个中心用二分法查找以其为中心的最长回文半径。二分半径长度len通过比较正向子串哈希和反向子串哈希是否相等来判断该半径下的子串是否为回文。时间复杂度枚举中心 O(N)二分查找 O(logN)哈希比较 O(1)总复杂度 O(N logN)。代码实现#include iostream #include string #include vector #include algorithm using namespace std; typedef unsigned long long ULL; const ULL P 131; class DoubleHash { public: string s; int n; vectorULL h1, h2; // h1: 正向哈希 h2: 反向哈希 vectorULL p; DoubleHash(const string str) : s(str), n(str.size()) { h1.resize(n 1, 0); h2.resize(n 1, 0); p.resize(n 1, 1); // 计算正向哈希 for (int i 1; i n; i) { p[i] p[i - 1] * P; h1[i] h1[i - 1] * P s[i - 1]; } // 计算反向哈希 for (int i 1; i n; i) { h2[i] h2[i - 1] * P s[n - i]; } } // 获取正向子串 s[l...r] 的哈希值 ULL getHash1(int l, int r) { return h1[r 1] - h1[l] * p[r - l 1]; } // 获取反向子串 s[l...r] 的哈希值 (注意坐标转换) ULL getHash2(int l, int r) { // 原串 s[l...r] 在反向串中对应 s[n-1-r ... n-1-l] int rev_l n - 1 - r; int rev_r n - 1 - l; return h2[rev_r 1] - h2[rev_l] * p[rev_r - rev_l 1]; } // 判断子串 s[l...r] 是否是回文 bool isPalindrome(int l, int r) { return getHash1(l, r) getHash2(l, r); } }; string longestPalindrome(string s) { int n s.size(); if (n 1) return s; DoubleHash dh(s); int start 0, maxLen 1; // 枚举中心点 for (int center 0; center n; center) { // 奇数长度回文中心为 center int left 0, right min(center, n - 1 - center); while (left right) { int mid (left right 1) 1; if (dh.isPalindrome(center - mid, center mid)) { left mid; } else { right mid - 1; } } int len 2 * left 1; if (len maxLen) { maxLen len; start center - left; } // 偶数长度回文中心为 center 和 center1 之间 if (center 1 n s[center] s[center 1]) { left 0; right min(center, n - 2 - center); while (left right) { int mid (left right 1) 1; if (dh.isPalindrome(center - mid, center 1 mid)) { left mid; } else { right mid - 1; } } len 2 * left 2; if (len maxLen) { maxLen len; start center - left; } } } return s.substr(start, maxLen); } int main() { string test1 babad; string test2 cbbd; cout 测试1: \ test1 \ - \ longestPalindrome(test1) \ endl; cout 测试2: \ test2 \ - \ longestPalindrome(test2) \ endl; return 0; }7. 常见问题与调试技巧Q1: 哈希冲突了怎么办A1: 首先确保使用了足够大的质数作为进制P和模数M。最有效的方法是使用双哈希即用两组不同的(P, M)分别计算哈希值只有当两个哈希值都相等时才认为字符串相等。可以将两个哈希值组成一个pairULL, ULL来使用。Q2: KMP的next数组有的版本从-1开始有的从0开始有什么区别A2: 这只是实现上的细节差异核心思想一致。next[0] -1表示当模式串第一个字符就失配时文本串指针i需要后移模式串指针j被重置为-1然后i, j变成0。代码中while循环条件常写为while (j 0 P[i] ! P[j])。next[0] 0如上文实现表示长度为1的子串没有真前缀/后缀。匹配时回退逻辑稍有不同但最终效果等价。选择一种并理解其状态转移即可。Q3: 如何调试KMP算法A3:打印next数组首先验证你计算的next数组是否正确。可以手动计算几个简单字符串的next数组进行比对。模拟单步执行在匹配循环中打印出每一步的i(文本串索引),j(模式串索引),T[i],P[j]的值对照算法流程手动模拟看指针跳转是否符合预期。使用简单测试用例从Taaaaa,Paa这样的简单例子开始测试。Q4: 字符串下标是从0开始还是1开始A4: 在C中string类型下标从0开始。本文所有代码和讲解均使用0-基索引。在构建前缀数组(h,next)时我们通常让h[i]对应原串s[0...i-1]这是为了公式推导和计算的方便。务必在代码中保持逻辑一致否则极易出错。8. 工程实践与最佳建议封装工具类在竞赛或项目中将字符串哈希和KMP算法封装成独立的类或函数模板。这样在主逻辑中只需关注调用提高代码复用性和整洁度。注意数据范围与溢出哈希运算中使用unsigned long long让其自然溢出模2^64是最方便的做法。如果使用固定模数如1e97务必在每次乘法和加法后取模。KMP算法中next数组和匹配循环的索引不要越界。理解优于记忆不要死记硬背next数组的构建代码或哈希公式。花时间理解其背后的状态转移和前缀后缀公共元素的概念这样才能在遇到变种题目时灵活应对。结合其他算法字符串问题常常不是孤立的。哈希可以结合二分答案、滑动窗口KMP的next数组可以用于求解字符串周期。掌握这些组合技巧能解决更复杂的问题。从暴力法出发在思考优化算法前先想清楚暴力解法O(N^2)或O(N^3)怎么做。这能帮你理清问题本质并明确优化方向如何减少重复比较、如何避免指针回退。字符串算法的学习路径可以遵循理解基础概念 - 掌握暴力解法 - 学习经典优化算法哈希、KMP- 练习典型例题 - 探索扩展算法字典树、AC自动机、后缀数组等。将第九天的哈希与KMP真正内化你就为后续更复杂的字符串与文本处理问题打下了坚实的基础。多写代码多模拟多总结在不断的实践中这些精妙的算法思想将成为你解决问题的本能反应。