尧图网站开发 
如果你正在准备算法竞赛或者刷题时被字符串问题卡住那么这篇文章就是为你准备的。字符串处理是算法竞赛中最基础、最频繁出现但也最容易失分的领域之一。很多人以为字符串就是简单的strcmp和substr直到在比赛中遇到“大整数加法”、“最长回文子串”或“模式匹配”时才发现自己连暴力解法都写不对。本文基于西安交通大学ACM算法竞赛小学期课程的第九天内容——“字符串”专题但绝不仅仅是复述课件。我们将深入探讨两个在竞赛和面试中出场率极高的核心算法哈希Hash和KMPKnuth-Morris-Pratt。你会发现它们解决的远不止“比较字符串是否相等”这么简单。哈希能让你在O(1)时间内判断任意子串是否相等是解决复杂字符串统计、去重、匹配问题的利器而KMP则优雅地解决了经典的模式匹配问题其核心的next数组思想更是动态规划的雏形。更重要的是本文将采用“场景驱动”的方式。我不会只告诉你算法是什么而是会带你经历1没有这些算法时我们的暴力解法有多低效2算法是如何一步步优化解决核心痛点的3在真实的竞赛题和LeetCode题中如何识别并使用它们4亲手实现时有哪些“坑”必须避开比如哈希冲突、next数组的两种定义。读完本文你将能清晰理解字符串哈希和KMP算法的原理、适用场景及局限性。独立手写这两个算法的核心代码模板并应用于相关问题。掌握在ACM模式下的C字符串输入输出技巧避免因IO问题丢分。获得一套解决字符串问题的系统性思路而不仅仅是两个孤立的算法。1. 字符串问题算法竞赛中的“基本功”与“分水岭”在算法竞赛中字符串问题常常扮演着“基本功检验器”和“实力分水岭”的角色。说它是基本功因为几乎每场比赛都离不开字符串的读入、处理和输出。说它是分水岭因为很多中等难度的问题其核心优化点就落在高效的字符串比较或匹配上。一个典型的误区许多初学者认为C的string类或者Python的字符串操作已经足够强大内置的find、substr等函数可以解决一切。然而在算法竞赛的约束下数据规模常达到10^5甚至10^6级别这些内置方法的复杂度往往是O(N)或O(N^2)极易导致超时TLE。我们面临的核心痛点快速子串比较给定一个长字符串S需要频繁地询问S的某个子串S[l1..r1]是否等于另一个子串S[l2..r2]。暴力比较每次需要O(子串长度)总复杂度无法承受。高效模式匹配在一个文本串T中查找一个模式串P所有出现的位置。朴素的暴力匹配算法复杂度为O(|T|*|P|)当两者都很大时不可行。大整数运算题目给出的整数远超long long范围需要用字符串表示并进行加、减、乘运算。复杂的字符串统计如统计不同子串数量、寻找最长回文子串、字符串循环同构等。字符串哈希和KMP算法正是为了解决前两个痛点而生的“重型武器”。理解它们是你从“暴力搜索”选手迈向“高效算法”选手的关键一步。2. 核心概念当字符串变成“数字”——字符串哈希2.1 哈希的思想化繁为简的映射哈希的核心思想是将一个可能很复杂、很大的数据比如一个长字符串通过一个函数哈希函数映射到一个较小范围的整数哈希值上。理想情况下不同的数据映射到不同的整数。这样我们比较两个字符串是否相等就转化为了比较两个整数是否相等时间复杂度从O(N)降到了O(1)。关键挑战哈希冲突。不同的字符串可能映射到相同的哈希值。在竞赛中我们通过精心选择哈希函数和参数可以将冲突概率降到极低视为“几乎不可能发生”。2.2 字符串哈希的常见实现多项式滚动哈希最常用且高效的字符串哈希方法是“多项式滚动哈希”Rolling Hash。我们把字符串看作一个P进制的数。假设字符串S “cba”字符映射为数字a1, b2, c3注意避免0。我们可以将其视为一个3进制数hash(“cba”) 3 * P^2 2 * P^1 1 * P^0。其中P是一个自选的进制基数通常取一个质数如131, 13331等。计算出的哈希值可能很大所以我们再对一个较大的质数M如2^64,1e97取模将结果控制在一定范围内。为什么能“滚动”假设我们已经预处理了字符串S每个前缀的哈希值H[i]表示S[0..i-1]的哈希。 那么子串S[l..r]的哈希值可以通过前缀哈希快速计算hash(S[l..r]) H[r1] - H[l] * P^(r-l1)这个公式可以在O(1)时间内完成实现了子串哈希的快速获取。2.3 KMP算法匹配失败时如何“智能回退”KMP算法解决的是单模式串匹配问题。它的核心优势在于当匹配失败时模式串指针不是简单地回溯到开头而是利用已经匹配成功部分的信息跳转到一个特定的位置继续匹配。这个“特定的位置”信息存储在一个叫做next数组或称fail数组的表中。next数组的含义对于模式串Pnext[i]表示子串P[0..i-1]中最长的、相等的前缀和后缀的长度注意这个长度小于i。 例如模式串P “ababc”next[0] -1(或0取决于定义这是KMP最容易混淆的点之一下文会详解)next[1] 0(“a” 无公共前后缀)next[2] 0(“ab” 前缀”a”和后缀”b”不等)next[3] 1(“aba” 最长公共前后缀是”a”长度为1)next[4] 2(“abab” 最长公共前后缀是”ab”长度为2)有了next数组在文本串T中匹配时如果T[i]和P[j]失配我们不是将i和j都回溯而是令j next[j]i不变继续比较。这避免了文本串指针i的回退将匹配复杂度从O(N*M)优化到了O(NM)。3. 环境准备与代码框架本文所有代码示例均基于C语言这是ACM/ICPC及大多数算法竞赛的主流语言。你需要准备编译器支持C11及以上标准的编译器如g, clang。开发环境任何你熟悉的IDE或文本编辑器如VS Code, CLion, Dev-C等均可。核心头文件iostream,string,vector,algorithm。输入输出在竞赛中为了追求极致速度通常使用scanf/printf或关闭同步流的cin/cout。本文示例将采用更易读的cin/cout并给出加速建议。一个通用的竞赛向C代码框架#include iostream #include string #include vector using namespace std; // 关闭cin/cout与stdio的同步并解除绑定可以大幅提升输入输出速度 static const int _ []() { ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }(); int main() { // 你的代码逻辑 string s; cin s; // ... 处理字符串s cout result endl; return 0; }注意一旦使用了ios::sync_with_stdio(false);就不能再混用cin/cout和scanf/printf。4. 字符串哈希从原理到实战4.1 哈希函数设计与实现我们选择P 131或13331模数M取2^64。利用Cunsigned long long的自然溢出特性可以自动实现模2^64运算既快又好写。步骤1预处理前缀哈希和幂数组typedef unsigned long long ULL; const int P 131; // 进制基数 vectorULL h; // h[i] 存储前i个字符的哈希值即S[0..i-1] vectorULL p; // p[i] 存储 P^i void initHash(const string s) { int n s.length(); h.resize(n 1, 0); p.resize(n 1, 0); p[0] 1; // P^0 1 for (int i 1; i n; i) { h[i] h[i-1] * P (s[i-1] - a 1); // 假设字符串由小写字母构成 p[i] p[i-1] * P; } }关键点字符映射s[i-1] - a 1。这里加1是为了避免‘a’映射为0导致“a”和“aa”等字符串哈希值可能相同的问题。h[i]对应的是s[0]到s[i-1]即前i个字符。步骤2计算任意子串的哈希值// 获取子串 s[l..r] 的哈希值下标从0开始 ULL getHash(int l, int r) { // 公式hash(s[l..r]) h[r1] - h[l] * p[r-l1] return h[r 1] - h[l] * p[r - l 1]; }这个getHash函数是字符串哈希的灵魂它让我们能在O(1)时间内得到任意子串的“指纹”。4.2 应用示例1快速判断子串是否相等问题给定字符串S进行Q次询问每次询问两个子串[l1, r1]和[l2, r2]是否完全相同。bool isSameSubstr(const string s, int l1, int r1, int l2, int r2) { // 前提已经对字符串s执行了 initHash(s) if (r1 - l1 ! r2 - l2) return false; // 长度不同直接返回false return getHash(l1, r1) getHash(l2, r2); }复杂度预处理O(N)每次询问O(1)。如果暴力比较每次询问需要O(子串长度)总复杂度O(Q*N)在N, Q都为10^5级别时完全无法通过。4.3 应用示例2求解最长回文子串二分哈希回文串判断是哈希的经典应用。我们可以用哈希在O(1)时间内判断一个子串是否是回文串。 思路预处理原串S的正向哈希再预处理其反向串S的正向哈希。对于S的任意子串其正向哈希值应等于其在S中对应子串的正向哈希值。string longestPalindrome(const string s) { int n s.length(); if (n 0) return ; initHash(s); // 正向哈希 string rev_s s; reverse(rev_s.begin(), rev_s.end()); initHash(rev_s); // 反向哈希注意这里需要另一套 h_rev 和 p_rev为简洁省略具体实现 int start 0, maxLen 1; // 中心扩展法结合哈希验证复杂度 O(N log N) for (int i 0; i n; i) { // 奇数长度回文以i为中心 int low 1, high min(i1, n-i); while (low high) { int mid (low high) / 2; int l i - mid 1; int r i mid - 1; if (getHash(l, r) getRevHash(n-1-r, n-1-l)) { // 判断正反哈希 if (2*mid-1 maxLen) { maxLen 2*mid-1; start l; } low mid 1; } else { high mid - 1; } } // 偶数长度回文以i和i1为中心代码类似略 } return s.substr(start, maxLen); }注意这是一种“二分答案哈希验证”的方法比纯中心扩展法在判断回文时更高效。更优的Manacher算法可以在O(N)内解决但哈希解法思路更通用易于理解和实现。5. KMP算法彻底理解next数组与匹配过程5.1 next数组的两种定义与实现这是KMP最易错点。主要有两种主流定义以0下标为例定义A前缀函数next[i]表示子串P[0..i]中最长的、相等的前缀和后缀的长度长度可以等于i1吗不行必须小于。通常next[0] 0。定义B失配指针next[i]表示当模式串在位置i匹配失败时下一个应该跳转去匹配的位置。通常next[0] -1。定义Bnext[0] -1的实现更常见也更容易融入匹配流程。下面给出这种定义的构建代码vectorint buildNext(const string pattern) { int m pattern.length(); vectorint next(m, 0); next[0] -1; // 初始化 int i 0, j -1; // i是当前主串指针后缀尾j是当前匹配的前缀尾也是next[i]的值 while (i m - 1) { // 注意是 m-1因为 next[m-1] 由 im-2 时算出 if (j -1 || pattern[i] pattern[j]) { // 匹配成功或者j回到起点 i; j; // 核心优化如果跳转后的字符和当前字符相同则失配时跳转会连续发生。 // 可以直接跳到更前面的位置。这是KMP算法常被忽略的优化点。 if (pattern[i] ! pattern[j]) { next[i] j; } else { next[i] next[j]; } } else { // 匹配失败j跳转到next[j] j next[j]; } } return next; }代码解释i遍历模式串j表示当前已匹配的前缀长度。if (pattern[i] pattern[j])当前字符匹配则公共前后缀长度可以增加1。else { j next[j]; }失配时利用已计算的next信息回退j而不是暴力重置为0。优化部分if (pattern[i] ! pattern[j])如果跳转后的字符和当前字符相同那么这次跳转后必然还会失配所以直接跳到next[j]。这个优化能避免最坏情况下的退化。5.2 KMP匹配主流程有了next数组匹配过程就非常清晰了。vectorint kmpSearch(const string text, const string pattern) { vectorint positions; // 存储所有匹配的起始位置 int n text.length(), m pattern.length(); if (m 0) return positions; // 模式串为空 vectorint next buildNext(pattern); int i 0, j 0; // i遍历文本串j遍历模式串 while (i n) { if (j -1 || text[i] pattern[j]) { // 当前字符匹配成功 i; j; } else { // 失配模式串指针j跳转 j next[j]; } if (j m) { // 找到一个完整匹配 positions.push_back(i - m); // 记录起始下标 j next[j]; // 继续寻找下一个匹配注意这里jm需要跳转 } } return positions; }5.3 应用示例在文本中查找所有模式串出现位置int main() { string text ababcababcababc; string pattern ababc; vectorint matches kmpSearch(text, pattern); cout Pattern \ pattern \ found at positions: ; for (int pos : matches) { cout pos ; } cout endl; // 输出Pattern ababc found at positions: 0 5 10 return 0; }6. 综合实战解决LeetCode/竞赛经典问题6.1 LeetCode 214. 最短回文串字符串哈希问题给定一个字符串s你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。思路问题等价于找到原串s的最长前缀回文串。假设这个前缀回文串长度为len那么我们只需要将s中len之后的部分反转并添加到原串前面即可。寻找最长前缀回文串正是字符串哈希的用武之地。string shortestPalindrome(string s) { int n s.length(); if (n 0) return ; // 1. 预处理正向哈希 vectorULL h(n1, 0), p(n1, 0); p[0] 1; for (int i 1; i n; i) { h[i] h[i-1] * P (s[i-1] - a 1); p[i] p[i-1] * P; } // 2. 预处理反向哈希将s反转 string rev_s s; reverse(rev_s.begin(), rev_s.end()); vectorULL hr(n1, 0); for (int i 1; i n; i) { hr[i] hr[i-1] * P (rev_s[i-1] - a 1); } // 3. 寻找最长的前缀回文串长度 int maxLen 0; for (int i n; i 1; i--) { // 从长到短检查前缀 // 原串前缀 s[0..i-1] 的哈希 ULL hash_s h[i]; // 反向串中对应部分 rev_s[n-i..n-1] 的哈希 // rev_s中对应s[0..i-1]的部分是 rev_s[n-i..n-1] ULL hash_rev hr[n] - hr[n-i] * p[i]; if (hash_s hash_rev) { maxLen i; break; } } // 4. 构造结果 string need_to_add s.substr(maxLen); reverse(need_to_add.begin(), need_to_add.end()); return need_to_add s; }6.2 竞赛题大整数加法字符串处理基础虽然哈希和KMP是高级主题但字符串处理基础不容忽视。大整数加法是经典问题。string addStrings(string num1, string num2) { int i num1.length() - 1, j num2.length() - 1; int carry 0; string result ; while (i 0 || j 0 || carry) { int digit1 (i 0) ? num1[i] - 0 : 0; int digit2 (j 0) ? num2[j] - 0 : 0; int sum digit1 digit2 carry; carry sum / 10; result.push_back((sum % 10) 0); i--; j--; } reverse(result.begin(), result.end()); return result; }关键点从最低位字符串末尾开始计算处理进位最后反转结果字符串。7. 常见问题与排查思路问题现象可能原因排查方式解决方案字符串哈希冲突导致错误判断1. 进制P或模数M选择不当。2. 字符映射到0如‘a’映射为0。使用双哈希两个不同的P和M进行验证。1. 使用更大的质数作为P如13331, 131等。2. 字符映射时s[i]-‘a’1确保非零。3. 对于极高精度要求实现双哈希。KMP算法陷入死循环或越界next数组计算错误特别是j next[j]时j可能为-1未正确处理。单步调试打印i,j,next数组的值。检查buildNext函数中while循环的边界条件以及if (j -1 ...)的判断是否齐全。KMP能找到部分匹配但漏掉一些next数组定义混淆next[0] 0还是-1导致匹配逻辑错位。用一个简单例子如T“aaaa”,P“aa”手动模拟你的算法。统一并彻底理解你采用的next数组定义。建议使用next[0] -1的定义代码更清晰。哈希获取子串值错误计算子串哈希的公式h[r1] - h[l] * p[r-l1]下标写错。用一个小字符串如“abc”手动计算每个前缀哈希和幂验证getHash函数。牢记h[i]对应前i个字符下标0到i-1。公式务必准确。处理含非小写字母的字符串时哈希错误字符映射函数只考虑了‘a’~‘z’。检查输入字符串是否包含数字、大写字母或其他字符。扩展映射关系例如使用字符的ASCII码直接作为映射值但要注意0值问题或建立更完整的映射表。ACM模式下字符串读入出错未处理行末空格、换行或cin与getline混用导致。在本地用边界用例测试空行、多空格。1. 统一使用cin string忽略空白符或getline(cin, string)。2. 使用while (cin s)处理不定数量输入。8. 最佳实践与工程建议模板化代码将字符串哈希的initHash和getHash以及KMP的buildNext和kmpSearch封装成函数或类。在竞赛中直接套用节省时间并减少错误。class StringHash { public: StringHash(const string s) { // 初始化代码 } ULL get(int l, int r) { // 获取哈希值 } private: vectorULL h, p; };双哈希策略对于极其关键、不能接受任何冲突的场景如高价值比赛使用双哈希。即用两套不同的(P, M)计算两个哈希值只有当两个哈希值都相等时才判定字符串相等。这能将冲突概率降到极低。理解优于死记不要死记next数组的代码。理解其代表的是“最长公共前后缀”并能在纸上对一个简单模式串如“aabaaac”推导出next数组。理解后代码自然能写出来。注意输入规模使用字符串哈希时预处理p数组幂次的大小应与字符串长度相同。如果字符串长度达到10^6p数组也需要10^61的大小确保不会越界。KMP的扩展应用next数组本身蕴含了字符串的周期信息。对于一个长度为n的字符串S如果n % (n - next[n]) 0那么该字符串可以由其长度为n - next[n]的前缀重复构成。这在解决字符串周期问题时非常有用。综合选择算法快速判断子串相等、回文、字符串搜索非精确匹配- 优先考虑字符串哈希。单模式串精确匹配、求字符串周期- 优先考虑KMP。对于多模式串匹配则需要更复杂的算法如字典树Trie或AC自动机。字符串是算法世界的基石而哈希与KMP是打磨这块基石的两把利刃。它们将看似复杂的字符串比较和匹配问题转化为了可预计算、可快速查询的数值问题或状态跳转问题。掌握它们意味着你在处理字符串相关问题时拥有了从O(N²)到O(N)或O(N log N)的降维打击能力。真正的掌握源于实践。建议你在LeetCode上搜索“字符串哈希”和“KMP”相关题目进行练习。尝试用字符串哈希解决“ 最长重复子串 ”这类问题。尝试用KMP解决“ 重复的子字符串 ”这类问题。最后记住所有高级算法都建立在扎实的基础之上。在追求哈希和KMP的同时务必确保自己能毫无障碍地实现字符串反转、分割、大整数加减等基础操作。当你把这些工具融会贯通形成自己的“算法工具箱”时任何字符串问题都将不再令你畏惧。 
如果你正在准备算法竞赛或者刷题时被字符串问题卡住那么这篇文章就是为你准备的。字符串处理是算法竞赛中最基础、最频繁出现但也最容易失分的领域之一。很多人以为字符串就是简单的strcmp和substr直到在比赛中遇到“大整数加法”、“最长回文子串”或“模式匹配”时才发现自己连暴力解法都写不对。本文基于西安交通大学ACM算法竞赛小学期课程的第九天内容——“字符串”专题但绝不仅仅是复述课件。我们将深入探讨两个在竞赛和面试中出场率极高的核心算法哈希Hash和KMPKnuth-Morris-Pratt。你会发现它们解决的远不止“比较字符串是否相等”这么简单。哈希能让你在O(1)时间内判断任意子串是否相等是解决复杂字符串统计、去重、匹配问题的利器而KMP则优雅地解决了经典的模式匹配问题其核心的next数组思想更是动态规划的雏形。更重要的是本文将采用“场景驱动”的方式。我不会只告诉你算法是什么而是会带你经历1没有这些算法时我们的暴力解法有多低效2算法是如何一步步优化解决核心痛点的3在真实的竞赛题和LeetCode题中如何识别并使用它们4亲手实现时有哪些“坑”必须避开比如哈希冲突、next数组的两种定义。读完本文你将能清晰理解字符串哈希和KMP算法的原理、适用场景及局限性。独立手写这两个算法的核心代码模板并应用于相关问题。掌握在ACM模式下的C字符串输入输出技巧避免因IO问题丢分。获得一套解决字符串问题的系统性思路而不仅仅是两个孤立的算法。1. 字符串问题算法竞赛中的“基本功”与“分水岭”在算法竞赛中字符串问题常常扮演着“基本功检验器”和“实力分水岭”的角色。说它是基本功因为几乎每场比赛都离不开字符串的读入、处理和输出。说它是分水岭因为很多中等难度的问题其核心优化点就落在高效的字符串比较或匹配上。一个典型的误区许多初学者认为C的string类或者Python的字符串操作已经足够强大内置的find、substr等函数可以解决一切。然而在算法竞赛的约束下数据规模常达到10^5甚至10^6级别这些内置方法的复杂度往往是O(N)或O(N^2)极易导致超时TLE。我们面临的核心痛点快速子串比较给定一个长字符串S需要频繁地询问S的某个子串S[l1..r1]是否等于另一个子串S[l2..r2]。暴力比较每次需要O(子串长度)总复杂度无法承受。高效模式匹配在一个文本串T中查找一个模式串P所有出现的位置。朴素的暴力匹配算法复杂度为O(|T|*|P|)当两者都很大时不可行。大整数运算题目给出的整数远超long long范围需要用字符串表示并进行加、减、乘运算。复杂的字符串统计如统计不同子串数量、寻找最长回文子串、字符串循环同构等。字符串哈希和KMP算法正是为了解决前两个痛点而生的“重型武器”。理解它们是你从“暴力搜索”选手迈向“高效算法”选手的关键一步。2. 核心概念当字符串变成“数字”——字符串哈希2.1 哈希的思想化繁为简的映射哈希的核心思想是将一个可能很复杂、很大的数据比如一个长字符串通过一个函数哈希函数映射到一个较小范围的整数哈希值上。理想情况下不同的数据映射到不同的整数。这样我们比较两个字符串是否相等就转化为了比较两个整数是否相等时间复杂度从O(N)降到了O(1)。关键挑战哈希冲突。不同的字符串可能映射到相同的哈希值。在竞赛中我们通过精心选择哈希函数和参数可以将冲突概率降到极低视为“几乎不可能发生”。2.2 字符串哈希的常见实现多项式滚动哈希最常用且高效的字符串哈希方法是“多项式滚动哈希”Rolling Hash。我们把字符串看作一个P进制的数。假设字符串S “cba”字符映射为数字a1, b2, c3注意避免0。我们可以将其视为一个3进制数hash(“cba”) 3 * P^2 2 * P^1 1 * P^0。其中P是一个自选的进制基数通常取一个质数如131, 13331等。计算出的哈希值可能很大所以我们再对一个较大的质数M如2^64,1e97取模将结果控制在一定范围内。为什么能“滚动”假设我们已经预处理了字符串S每个前缀的哈希值H[i]表示S[0..i-1]的哈希。 那么子串S[l..r]的哈希值可以通过前缀哈希快速计算hash(S[l..r]) H[r1] - H[l] * P^(r-l1)这个公式可以在O(1)时间内完成实现了子串哈希的快速获取。2.3 KMP算法匹配失败时如何“智能回退”KMP算法解决的是单模式串匹配问题。它的核心优势在于当匹配失败时模式串指针不是简单地回溯到开头而是利用已经匹配成功部分的信息跳转到一个特定的位置继续匹配。这个“特定的位置”信息存储在一个叫做next数组或称fail数组的表中。next数组的含义对于模式串Pnext[i]表示子串P[0..i-1]中最长的、相等的前缀和后缀的长度注意这个长度小于i。 例如模式串P “ababc”next[0] -1(或0取决于定义这是KMP最容易混淆的点之一下文会详解)next[1] 0(“a” 无公共前后缀)next[2] 0(“ab” 前缀”a”和后缀”b”不等)next[3] 1(“aba” 最长公共前后缀是”a”长度为1)next[4] 2(“abab” 最长公共前后缀是”ab”长度为2)有了next数组在文本串T中匹配时如果T[i]和P[j]失配我们不是将i和j都回溯而是令j next[j]i不变继续比较。这避免了文本串指针i的回退将匹配复杂度从O(N*M)优化到了O(NM)。3. 环境准备与代码框架本文所有代码示例均基于C语言这是ACM/ICPC及大多数算法竞赛的主流语言。你需要准备编译器支持C11及以上标准的编译器如g, clang。开发环境任何你熟悉的IDE或文本编辑器如VS Code, CLion, Dev-C等均可。核心头文件iostream,string,vector,algorithm。输入输出在竞赛中为了追求极致速度通常使用scanf/printf或关闭同步流的cin/cout。本文示例将采用更易读的cin/cout并给出加速建议。一个通用的竞赛向C代码框架#include iostream #include string #include vector using namespace std; // 关闭cin/cout与stdio的同步并解除绑定可以大幅提升输入输出速度 static const int _ []() { ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }(); int main() { // 你的代码逻辑 string s; cin s; // ... 处理字符串s cout result endl; return 0; }注意一旦使用了ios::sync_with_stdio(false);就不能再混用cin/cout和scanf/printf。4. 字符串哈希从原理到实战4.1 哈希函数设计与实现我们选择P 131或13331模数M取2^64。利用Cunsigned long long的自然溢出特性可以自动实现模2^64运算既快又好写。步骤1预处理前缀哈希和幂数组typedef unsigned long long ULL; const int P 131; // 进制基数 vectorULL h; // h[i] 存储前i个字符的哈希值即S[0..i-1] vectorULL p; // p[i] 存储 P^i void initHash(const string s) { int n s.length(); h.resize(n 1, 0); p.resize(n 1, 0); p[0] 1; // P^0 1 for (int i 1; i n; i) { h[i] h[i-1] * P (s[i-1] - a 1); // 假设字符串由小写字母构成 p[i] p[i-1] * P; } }关键点字符映射s[i-1] - a 1。这里加1是为了避免‘a’映射为0导致“a”和“aa”等字符串哈希值可能相同的问题。h[i]对应的是s[0]到s[i-1]即前i个字符。步骤2计算任意子串的哈希值// 获取子串 s[l..r] 的哈希值下标从0开始 ULL getHash(int l, int r) { // 公式hash(s[l..r]) h[r1] - h[l] * p[r-l1] return h[r 1] - h[l] * p[r - l 1]; }这个getHash函数是字符串哈希的灵魂它让我们能在O(1)时间内得到任意子串的“指纹”。4.2 应用示例1快速判断子串是否相等问题给定字符串S进行Q次询问每次询问两个子串[l1, r1]和[l2, r2]是否完全相同。bool isSameSubstr(const string s, int l1, int r1, int l2, int r2) { // 前提已经对字符串s执行了 initHash(s) if (r1 - l1 ! r2 - l2) return false; // 长度不同直接返回false return getHash(l1, r1) getHash(l2, r2); }复杂度预处理O(N)每次询问O(1)。如果暴力比较每次询问需要O(子串长度)总复杂度O(Q*N)在N, Q都为10^5级别时完全无法通过。4.3 应用示例2求解最长回文子串二分哈希回文串判断是哈希的经典应用。我们可以用哈希在O(1)时间内判断一个子串是否是回文串。 思路预处理原串S的正向哈希再预处理其反向串S的正向哈希。对于S的任意子串其正向哈希值应等于其在S中对应子串的正向哈希值。string longestPalindrome(const string s) { int n s.length(); if (n 0) return ; initHash(s); // 正向哈希 string rev_s s; reverse(rev_s.begin(), rev_s.end()); initHash(rev_s); // 反向哈希注意这里需要另一套 h_rev 和 p_rev为简洁省略具体实现 int start 0, maxLen 1; // 中心扩展法结合哈希验证复杂度 O(N log N) for (int i 0; i n; i) { // 奇数长度回文以i为中心 int low 1, high min(i1, n-i); while (low high) { int mid (low high) / 2; int l i - mid 1; int r i mid - 1; if (getHash(l, r) getRevHash(n-1-r, n-1-l)) { // 判断正反哈希 if (2*mid-1 maxLen) { maxLen 2*mid-1; start l; } low mid 1; } else { high mid - 1; } } // 偶数长度回文以i和i1为中心代码类似略 } return s.substr(start, maxLen); }注意这是一种“二分答案哈希验证”的方法比纯中心扩展法在判断回文时更高效。更优的Manacher算法可以在O(N)内解决但哈希解法思路更通用易于理解和实现。5. KMP算法彻底理解next数组与匹配过程5.1 next数组的两种定义与实现这是KMP最易错点。主要有两种主流定义以0下标为例定义A前缀函数next[i]表示子串P[0..i]中最长的、相等的前缀和后缀的长度长度可以等于i1吗不行必须小于。通常next[0] 0。定义B失配指针next[i]表示当模式串在位置i匹配失败时下一个应该跳转去匹配的位置。通常next[0] -1。定义Bnext[0] -1的实现更常见也更容易融入匹配流程。下面给出这种定义的构建代码vectorint buildNext(const string pattern) { int m pattern.length(); vectorint next(m, 0); next[0] -1; // 初始化 int i 0, j -1; // i是当前主串指针后缀尾j是当前匹配的前缀尾也是next[i]的值 while (i m - 1) { // 注意是 m-1因为 next[m-1] 由 im-2 时算出 if (j -1 || pattern[i] pattern[j]) { // 匹配成功或者j回到起点 i; j; // 核心优化如果跳转后的字符和当前字符相同则失配时跳转会连续发生。 // 可以直接跳到更前面的位置。这是KMP算法常被忽略的优化点。 if (pattern[i] ! pattern[j]) { next[i] j; } else { next[i] next[j]; } } else { // 匹配失败j跳转到next[j] j next[j]; } } return next; }代码解释i遍历模式串j表示当前已匹配的前缀长度。if (pattern[i] pattern[j])当前字符匹配则公共前后缀长度可以增加1。else { j next[j]; }失配时利用已计算的next信息回退j而不是暴力重置为0。优化部分if (pattern[i] ! pattern[j])如果跳转后的字符和当前字符相同那么这次跳转后必然还会失配所以直接跳到next[j]。这个优化能避免最坏情况下的退化。5.2 KMP匹配主流程有了next数组匹配过程就非常清晰了。vectorint kmpSearch(const string text, const string pattern) { vectorint positions; // 存储所有匹配的起始位置 int n text.length(), m pattern.length(); if (m 0) return positions; // 模式串为空 vectorint next buildNext(pattern); int i 0, j 0; // i遍历文本串j遍历模式串 while (i n) { if (j -1 || text[i] pattern[j]) { // 当前字符匹配成功 i; j; } else { // 失配模式串指针j跳转 j next[j]; } if (j m) { // 找到一个完整匹配 positions.push_back(i - m); // 记录起始下标 j next[j]; // 继续寻找下一个匹配注意这里jm需要跳转 } } return positions; }5.3 应用示例在文本中查找所有模式串出现位置int main() { string text ababcababcababc; string pattern ababc; vectorint matches kmpSearch(text, pattern); cout Pattern \ pattern \ found at positions: ; for (int pos : matches) { cout pos ; } cout endl; // 输出Pattern ababc found at positions: 0 5 10 return 0; }6. 综合实战解决LeetCode/竞赛经典问题6.1 LeetCode 214. 最短回文串字符串哈希问题给定一个字符串s你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。思路问题等价于找到原串s的最长前缀回文串。假设这个前缀回文串长度为len那么我们只需要将s中len之后的部分反转并添加到原串前面即可。寻找最长前缀回文串正是字符串哈希的用武之地。string shortestPalindrome(string s) { int n s.length(); if (n 0) return ; // 1. 预处理正向哈希 vectorULL h(n1, 0), p(n1, 0); p[0] 1; for (int i 1; i n; i) { h[i] h[i-1] * P (s[i-1] - a 1); p[i] p[i-1] * P; } // 2. 预处理反向哈希将s反转 string rev_s s; reverse(rev_s.begin(), rev_s.end()); vectorULL hr(n1, 0); for (int i 1; i n; i) { hr[i] hr[i-1] * P (rev_s[i-1] - a 1); } // 3. 寻找最长的前缀回文串长度 int maxLen 0; for (int i n; i 1; i--) { // 从长到短检查前缀 // 原串前缀 s[0..i-1] 的哈希 ULL hash_s h[i]; // 反向串中对应部分 rev_s[n-i..n-1] 的哈希 // rev_s中对应s[0..i-1]的部分是 rev_s[n-i..n-1] ULL hash_rev hr[n] - hr[n-i] * p[i]; if (hash_s hash_rev) { maxLen i; break; } } // 4. 构造结果 string need_to_add s.substr(maxLen); reverse(need_to_add.begin(), need_to_add.end()); return need_to_add s; }6.2 竞赛题大整数加法字符串处理基础虽然哈希和KMP是高级主题但字符串处理基础不容忽视。大整数加法是经典问题。string addStrings(string num1, string num2) { int i num1.length() - 1, j num2.length() - 1; int carry 0; string result ; while (i 0 || j 0 || carry) { int digit1 (i 0) ? num1[i] - 0 : 0; int digit2 (j 0) ? num2[j] - 0 : 0; int sum digit1 digit2 carry; carry sum / 10; result.push_back((sum % 10) 0); i--; j--; } reverse(result.begin(), result.end()); return result; }关键点从最低位字符串末尾开始计算处理进位最后反转结果字符串。7. 常见问题与排查思路问题现象可能原因排查方式解决方案字符串哈希冲突导致错误判断1. 进制P或模数M选择不当。2. 字符映射到0如‘a’映射为0。使用双哈希两个不同的P和M进行验证。1. 使用更大的质数作为P如13331, 131等。2. 字符映射时s[i]-‘a’1确保非零。3. 对于极高精度要求实现双哈希。KMP算法陷入死循环或越界next数组计算错误特别是j next[j]时j可能为-1未正确处理。单步调试打印i,j,next数组的值。检查buildNext函数中while循环的边界条件以及if (j -1 ...)的判断是否齐全。KMP能找到部分匹配但漏掉一些next数组定义混淆next[0] 0还是-1导致匹配逻辑错位。用一个简单例子如T“aaaa”,P“aa”手动模拟你的算法。统一并彻底理解你采用的next数组定义。建议使用next[0] -1的定义代码更清晰。哈希获取子串值错误计算子串哈希的公式h[r1] - h[l] * p[r-l1]下标写错。用一个小字符串如“abc”手动计算每个前缀哈希和幂验证getHash函数。牢记h[i]对应前i个字符下标0到i-1。公式务必准确。处理含非小写字母的字符串时哈希错误字符映射函数只考虑了‘a’~‘z’。检查输入字符串是否包含数字、大写字母或其他字符。扩展映射关系例如使用字符的ASCII码直接作为映射值但要注意0值问题或建立更完整的映射表。ACM模式下字符串读入出错未处理行末空格、换行或cin与getline混用导致。在本地用边界用例测试空行、多空格。1. 统一使用cin string忽略空白符或getline(cin, string)。2. 使用while (cin s)处理不定数量输入。8. 最佳实践与工程建议模板化代码将字符串哈希的initHash和getHash以及KMP的buildNext和kmpSearch封装成函数或类。在竞赛中直接套用节省时间并减少错误。class StringHash { public: StringHash(const string s) { // 初始化代码 } ULL get(int l, int r) { // 获取哈希值 } private: vectorULL h, p; };双哈希策略对于极其关键、不能接受任何冲突的场景如高价值比赛使用双哈希。即用两套不同的(P, M)计算两个哈希值只有当两个哈希值都相等时才判定字符串相等。这能将冲突概率降到极低。理解优于死记不要死记next数组的代码。理解其代表的是“最长公共前后缀”并能在纸上对一个简单模式串如“aabaaac”推导出next数组。理解后代码自然能写出来。注意输入规模使用字符串哈希时预处理p数组幂次的大小应与字符串长度相同。如果字符串长度达到10^6p数组也需要10^61的大小确保不会越界。KMP的扩展应用next数组本身蕴含了字符串的周期信息。对于一个长度为n的字符串S如果n % (n - next[n]) 0那么该字符串可以由其长度为n - next[n]的前缀重复构成。这在解决字符串周期问题时非常有用。综合选择算法快速判断子串相等、回文、字符串搜索非精确匹配- 优先考虑字符串哈希。单模式串精确匹配、求字符串周期- 优先考虑KMP。对于多模式串匹配则需要更复杂的算法如字典树Trie或AC自动机。字符串是算法世界的基石而哈希与KMP是打磨这块基石的两把利刃。它们将看似复杂的字符串比较和匹配问题转化为了可预计算、可快速查询的数值问题或状态跳转问题。掌握它们意味着你在处理字符串相关问题时拥有了从O(N²)到O(N)或O(N log N)的降维打击能力。真正的掌握源于实践。建议你在LeetCode上搜索“字符串哈希”和“KMP”相关题目进行练习。尝试用字符串哈希解决“ 最长重复子串 ”这类问题。尝试用KMP解决“ 重复的子字符串 ”这类问题。最后记住所有高级算法都建立在扎实的基础之上。在追求哈希和KMP的同时务必确保自己能毫无障碍地实现字符串反转、分割、大整数加减等基础操作。当你把这些工具融会贯通形成自己的“算法工具箱”时任何字符串问题都将不再令你畏惧。