这次我们聚焦西安交通大学 ACM 算法竞赛小学期课程的第九天内容——字符串专题。对于任何有志于算法竞赛的同学来说字符串处理都是必须跨越的一道坎。它不像动态规划那样抽象也不像图论那样复杂但却是最基础、最高频、也最容易在细节上“翻车”的考点。从简单的字符匹配到复杂的模式查找再到各种哈希技巧掌握字符串算法意味着你的代码在处理文本、数据解析等场景下将更加稳健高效。本文不是简单的知识点罗列而是旨在为你提供一套可落地、可验证的字符串算法实战指南。我们将重点关注哈希Hash和 KMP 这两个核心算法它们不仅是解决大量字符串问题的利器更是面试和竞赛中的常客。你会看到它们如何从原理走向代码如何应对各种边界条件以及在实际解题中如何灵活运用。无论你是刚开始接触 ACM 模式输入输出的新手还是希望巩固字符串算法基础的进阶选手这篇文章都将带你快速理清思路避开常见陷阱。1. 核心能力速览字符串专题重点在深入代码之前我们先快速把握本次字符串专题的核心要点与实战价值。能力项说明与实战意义核心算法哈希Hash与KMPKnuth-Morris-Pratt。前者用于快速匹配与查重后者用于高效的单模模式匹配。解决的核心问题1.快速判断两个字符串或子串是否相等哈希。2.在一个文本串中高效查找一个模式串的所有出现位置KMP。3. 处理大整数、循环节、最长回文子串等衍生问题。硬件/环境门槛极低。仅需标准的 C/Java/Python 编程环境如 GCC、JDK、CPython对算力无特殊要求重点在于算法逻辑本身。思维门槛中等。需要理解前缀哈希、滚动哈希的原理以及 KMP 中next 数组失配函数的构建与使用逻辑。典型应用场景1.ACM 竞赛题目字符串匹配、循环节、最长公共子串、回文串处理。2.工程开发文本编辑器查找功能、病毒特征码匹配、数据去重、版本控制中的文件差异比较。3.面试考点手写 KMP、实现字符串哈希、解决大数比较问题。关键难点1.哈希冲突的处理与哈希函数的设计。2.KMP next 数组的理解与正确编码。3.ACM 模式下的输入输出处理特别是大字符串的读取。学习目标能独立实现双哈希防冲突能默写 KMP 算法模板并应用于解决相应难度的 OJ 题目。2. 适用场景与使用边界字符串算法并非银弹了解其擅长与不擅长的场景能帮助你在解题时快速选择正确工具。适合谁用算法竞赛选手字符串是必考领域哈希和 KMP 是必须掌握的模板算法。准备技术面试的求职者尤其是后端、基础软件、安全等岗位手写字符串匹配算法是高频考题。需要处理文本数据的开发者当内置的string.find()性能成为瓶颈或需要更复杂的匹配逻辑时。能解决什么问题高效比较与查找在O(1)时间复杂度内比较任意两个子串是否相等哈希或在O(nm)时间内完成单模匹配KMP远优于朴素的O(n*m)。处理“大整数”将数字字符串通过哈希转化为可比较的整数轻松处理超出内置整数类型范围的大数比较问题。寻找循环节利用 KMP 的next数组可以巧妙求出字符串的最小循环节长度。配合其他算法哈希常作为“指纹”用于动态规划、二分答案等算法的状态记录或去重。不适合什么场景简单的、一次性的字符串操作直接使用编程语言内置的字符串库函数如strstr,indexOf,find更便捷。多模式匹配当需要同时在文本中查找多个模式串时应使用AC 自动机Aho-Corasick它是 KMP 在多模式下的扩展。带通配符或正则表达式的模糊匹配需要使用更专用的正则表达式引擎或动态规划。重要边界哈希冲突哈希算法不是完美的。不同的字符串有可能计算出相同的哈希值冲突。在竞赛中通常采用**双哈希使用两组不同的基数和模数**来将冲突概率降到极低足以通过测试。但在对绝对正确性要求极高的安全或金融场景哈希仅能用于快速筛选最终仍需逐字符比较确认。3. 环境准备与前置条件工欲善其事必先利其器。开始编码前请确保你的“作战环境”已就绪。编程语言选择C竞赛首选性能最优需熟悉std::string、std::vector和输入输出流 (cin/cout) 或scanf/printf。Java需熟悉String、StringBuilder类以及Scanner或BufferedReader进行输入。Python代码简洁但运行效率较低需注意大数据量下的性能问题。熟悉str类型和sys.stdin.read()。开发环境本地 IDE如 CodeBlocks, Dev-C, Visual Studio, IntelliJ IDEA, PyCharm 等。配置好编译运行环境。在线 OJOnline Judge用于测试和刷题。例如洛谷Luogu、力扣LeetCode、杭电 OJHDU、POJ 等。熟悉其 ACM 模式的输入输出格式至关重要。ACM 模式输入输出训练 这是许多新手的第一道坎。竞赛中程序需要从标准输入 (stdin) 持续读取数据直到文件结束 (EOF)并将结果输出到标准输出 (stdout)。C 示例#include iostream #include string using namespace std; int main() { string s; while (cin s) { // 循环读取直到 EOF // 处理字符串 s cout s.length() endl; // 输出结果 } return 0; }应对大字符串如果题目说明字符串长度可达10^5甚至10^6在 C 中应使用ios::sync_with_stdio(false); cin.tie(0);来关闭同步提升cin/cout速度或直接使用scanf和printf。思维准备 准备好纸笔用于推导哈希公式和 KMP 的next数组。理解胜过死记硬背。4. 字符串哈希String Hashing详解与实现字符串哈希的核心思想是将一个字符串映射成一个整数哈希值从而使得字符串的比较转化为整数的比较实现O(1)时间复杂度的子串匹配。4.1 原理前缀哈希与滚动哈希我们采用多项式哈希的方式。假设字符串s的下标从1开始长度为n。选择一个基数base例如p 131或13331通常取质数。选择一个模数mod例如mod 1e97或2^64利用 unsigned long long 自然溢出。定义哈希数组h[i]表示字符串s前i个字符的哈希值。有h[i] (h[i-1] * p s[i]) % mod同时我们预处理基数幂数组p_pow[i] (p_pow[i-1] * p) % mod其中p_pow[0] 1。有了h[]和p_pow[]我们可以O(1)计算出任意子串s[l..r]的哈希值hash(s[l..r]) (h[r] - h[l-1] * p_pow[r-l1] % mod mod) % mod公式理解h[r]包含了1..r的哈希h[l-1] * p_pow[r-l1]相当于将1..l-1的哈希值“左移”到与h[r]对齐的位置相减后即得到l..r的哈希。4.2 代码实现双哈希模板C单哈希存在冲突风险双哈希通过计算两个不同(base, mod)对的哈希值将冲突概率降到极低。#include iostream #include string #include vector using namespace std; typedef long long ll; typedef pairll, ll pll; // 用于存储双哈希值 class DoubleHash { private: string s; int n; ll base1, base2, mod1, mod2; vectorll pow1, pow2, h1, h2; void init() { pow1[0] pow2[0] 1; h1[0] h2[0] 0; for (int i 1; i n; i) { pow1[i] (pow1[i-1] * base1) % mod1; pow2[i] (pow2[i-1] * base2) % mod2; h1[i] (h1[i-1] * base1 s[i-1]) % mod1; // 注意s下标从0开始 h2[i] (h2[i-1] * base2 s[i-1]) % mod2; } } public: // 常用参数组合 DoubleHash(const string str) : s(str), n(str.length()) { base1 131; base2 13331; mod1 1000000007; mod2 1000000009; pow1.resize(n1); pow2.resize(n1); h1.resize(n1); h2.resize(n1); init(); } // 获取子串 [l, r) 的双哈希值左闭右开下标从0开始 pll get_hash(int l, int r) { if (l r) return {0, 0}; ll hash1 (h1[r] - h1[l] * pow1[r-l] % mod1 mod1) % mod1; ll hash2 (h2[r] - h2[l] * pow2[r-l] % mod2 mod2) % mod2; return {hash1, hash2}; } // 比较两个子串是否相等 bool equal(int l1, int r1, int l2, int r2) { return get_hash(l1, r1) get_hash(l2, r2); } }; int main() { string text abracadabra; DoubleHash dh(text); // 示例比较 abra 在文本中两次出现是否相同 // text[0..4) abra, text[7..11) abra if (dh.equal(0, 4, 7, 11)) { cout Substrings are equal! endl; } else { cout Substrings are NOT equal! endl; } // 获取子串哈希值 auto hash_val dh.get_hash(0, 4); cout Hash of abra: ( hash_val.first , hash_val.second ) endl; return 0; }4.3 功能测试与效果验证测试目的验证双哈希算法能正确、快速地比较子串。测试用例设计基础相等测试在已知字符串中比较明显相等的子串。基础不等测试比较明显不等的子串。边界测试空子串、整个字符串、单字符子串。长字符串压力测试生成一个长10^6的随机字符串多次随机选取子串进行比较验证性能与正确性可通过与暴力比较结果对照。操作与验证将上述DoubleHash类代码复制到你的编译器中。在main函数中构造不同的测试字符串和子串索引。运行程序观察输出是否符合预期。性能观察对于长字符串可以计算get_hash函数执行一百万次的时间感受O(1)查询的效率。常见“翻车”点下标处理代码中字符串下标是0-based且区间是左闭右开[l, r)务必与你的思维习惯统一否则极易出错。在解题时强烈建议固定使用一种下标体系。取模运算公式(h[r] - h[l-1] * p_pow[r-l1] % mod mod) % mod中的 mod再取模是为了防止负数。哈希冲突虽然双哈希已非常安全但理论上仍存在冲突。若在 OJ 上遇到无法解释的错误可尝试更换base和mod的值。5. KMP 算法详解与实现KMP 算法用于解决单模匹配问题给定文本串text和模式串pattern找出pattern在text中所有出现的位置。其核心是利用匹配失败时的信息通过一个next数组或称前缀函数、失配函数避免文本串指针的回退将时间复杂度降至O(nm)。5.1 原理next 数组的精髓next[i]的定义是对于模式串P的前i1个字符构成的子串P[0..i]其最长的、相等的、真前缀和真后缀的长度。真前缀不等于自身的前缀。真后缀不等于自身的后缀。例如模式串P ababci0子串a无真前缀/后缀next[0] 0。i1子串ab前缀{a}后缀{b}无相等next[1] 0。i2子串aba前缀{a,ab}后缀{a,ba}相等的最长串为a长度1next[2] 1。i3子串abab前缀{a,ab,aba}后缀{b,ab,bab}相等的最长串为ab长度2next[3] 2。i4子串ababc前缀{a,ab,aba,abab}后缀{c,bc,abc,babc}无相等next[4] 0。next数组的作用当在文本串T的第i位和模式串P的第j位匹配失败时j不必回溯到0而是回溯到next[j-1]。因为P[0..next[j-1]-1]已经和T[i-next[j-1]..i-1]匹配成功了。5.2 代码实现KMP 模板CKMP 的实现分为两步1. 构建next数组2. 利用next数组进行匹配。#include iostream #include string #include vector using namespace std; class KMP { private: string pattern; vectorint next; void build_next() { int m pattern.length(); next.resize(m, 0); for (int i 1, j 0; i m; i) { // 当 j0 且不匹配时利用已计算的 next 回退 j while (j 0 pattern[i] ! pattern[j]) { j next[j - 1]; } // 如果匹配j 前进一步 if (pattern[i] pattern[j]) { j; } // 记录 next[i] next[i] j; } } public: KMP(const string pat) : pattern(pat) { build_next(); } // 在文本串 text 中查找所有模式串出现的位置起始下标 vectorint search(const string text) { vectorint positions; int n text.length(); int m pattern.length(); if (m 0) return positions; // 空模式串 for (int i 0, j 0; i n; i) { // 不匹配时j 根据 next 数组回退 while (j 0 text[i] ! pattern[j]) { j next[j - 1]; } // 匹配时j 前进一步 if (text[i] pattern[j]) { j; } // 找到完整匹配 if (j m) { positions.push_back(i - m 1); // 记录起始位置 j next[j - 1]; // 继续寻找下一个匹配 } } return positions; } // 获取 next 数组用于调试或解决循环节问题 vectorint get_next_array() { return next; } }; int main() { string text ababcababcabababc; string pattern ababc; KMP kmp(pattern); vectorint res kmp.search(text); cout Pattern \ pattern \ found at positions: ; for (int pos : res) { cout pos ; } cout endl; // 输出 next 数组 vectorint next_arr kmp.get_next_array(); cout Next array: ; for (int val : next_arr) { cout val ; } cout endl; return 0; }5.3 功能测试与效果验证测试目的验证 KMP 算法能正确找到所有匹配位置并理解next数组。测试用例设计简单匹配文本串中包含明显的模式串。多重匹配模式串在文本串中重叠出现如aa在aaa中。无匹配文本串中不包含模式串。边界测试空文本串、空模式串、模式串长度大于文本串。长字符串压力测试生成长文本和长模式与暴力匹配算法 (O(n*m)) 对比运行时间。操作与验证复制上述KMP类代码。修改main函数中的text和pattern运行并检查输出位置是否正确。手动计算next数组与程序输出的next数组对比加深理解。性能观察构造一个长文本如10^6和一个中等长度模式如10^3使用 KMP 搜索感受其线性时间复杂度。可以尝试用暴力匹配做对比观察时间差异。常见“翻车”点next数组构建逻辑while循环中的回退条件是j 0且不匹配。next[i]记录的是匹配成功后j的值即最长相等前后缀长度。下标处理代码中下标从0开始。next[j-1]表示前j个字符组成子串的最长相等前后缀长度。匹配成功后继续搜索找到一次匹配后j next[j - 1]是关键这允许算法发现重叠的匹配例如在aaaa中找aa。6. 实战应用与题目解析掌握了模板关键还在于应用。下面结合典型问题展示如何运用哈希和 KMP。6.1 应用一求解字符串循环节KMP问题给定一个字符串s求其最小循环节长度。思路设字符串长度为len计算其next数组。如果len % (len - next[len-1]) 0则最小循环节长度为len - next[len-1]否则字符串没有循环节或视为整个字符串为一个循环节。原理len - next[len-1]是字符串中不参与“最长相等前后缀”的那部分长度它很可能就是最小循环节长度。如果整个字符串长度是它的整数倍则成立。代码片段int min_cycle_length(const string s) { int n s.length(); vectorint next(n, 0); for (int i 1, j 0; i n; i) { while (j 0 s[i] ! s[j]) j next[j-1]; if (s[i] s[j]) j; next[i] j; } int candidate n - next[n-1]; if (n % candidate 0) { return candidate; } else { return n; // 没有严格循环节 } }6.2 应用二大整数比较哈希问题给两个用字符串表示的大整数a和b长度可能超过10^4比较它们的大小。思路直接比较字符串先比长度长度相同再逐位比较。这是O(n)的完全可行。但这里我们用哈希来展示一种“另类”思路虽然杀鸡用牛刀但有助于理解哈希的通用性。我们可以将字符串视为一个base10的多项式计算其哈希值需要取一个足够大的模数如1e97。如果两个大整数的哈希值不同则它们一定不同如果哈希值相同在模数足够大且随机的情况下可以极大概率认为它们相同严格比较仍需逐位但竞赛中双哈希已足够。代码思路// 使用之前实现的 DoubleHash但 base 改为 10 class BigIntHash { // ... 类似 DoubleHashbase110, base213, mod11e97, mod21e99 }; bool is_equal(const string a, const string b) { if (a.length() ! b.length()) return false; BigIntHash hash_a(a), hash_b(b); return hash_a.get_hash(0, a.length()) hash_b.get_hash(0, b.length()); } // 注意此方法仅适用于判断相等不能直接用于比较大小。比较大小仍需先比长度再逐位。6.3 应用三最长回文子串哈希 二分问题求一个字符串的最长回文子串。思路枚举回文中心利用哈希O(1)判断子串是否相等结合二分查找确定以该中心能扩展的最大回文半径。时间复杂度O(n log n)。这是 Manacher 算法 (O(n)) 之外的一种重要解法充分体现了哈希的威力。核心代码逻辑预处理字符串的正向哈希和反向哈希。对于每个中心位置i可能是字符也可能是字符间间隙二分查找最大半径r使得s[i-r..i]的反转串等于s[i..ir]奇偶情况略有不同。通过比较正向子串哈希和反向子串哈希是否相等来判断。7. 资源占用与性能观察字符串算法本身不消耗显存/GPU资源其性能瓶颈在于时间复杂度和内存访问。时间复杂度哈希预处理O(n)每次子串比较O(1)。KMP构建next数组O(m)匹配过程O(n)总计O(nm)。务必与朴素算法 (O(n*m)) 对比理解效率提升。空间复杂度哈希需要O(n)的额外空间存储h和p_pow数组。KMP需要O(m)的额外空间存储next数组。对于长度10^6的字符串vectorint占用约4MBvectorlong long约8MB完全在内存承受范围内。性能测试建议使用计时代码 (chrono库) 测量不同长度字符串下哈希查询和 KMP 匹配的运行时间。对比不同base和mod对哈希冲突率的影响可以写脚本随机生成大量字符串进行测试。在 OJ 上提交相关题目关注“运行时间”和“内存占用”反馈这是最真实的性能观察。8. 常见问题与排查方法在实现和调试过程中你可能会遇到以下问题问题现象可能原因排查方式解决方案哈希比较结果错误1. 下标计算错误区间不对应。2. 取模运算出现负数未处理。3. 哈希冲突小概率。1. 使用简单短字符串手动计算哈希值对比。2. 输出中间h[]和p_pow[]数组检查。3. 换用双哈希或调整base/mod。1. 统一并固定下标体系推荐0-based左闭右开。2. 确保哈希公式(a - b mod) % mod。3. 实现双哈希。KMP 陷入死循环或越界1.while循环回退条件j 0写成了j 0。2. 访问next[j-1]时j可能为 0。1. 单步调试观察i和j的变化。2. 在循环开始和结束时打印i, j, next[j]的值。1. 仔细检查while循环条件确保j在回退时不会小于0。2. 确保next数组构建和匹配的逻辑完全一致。KMP 找不到所有匹配找到一次匹配后j回溯错误。应该是j next[j-1]而不是j 0。用包含重叠模式的字符串如aaaa中找aa测试。修正匹配成功后的j回溯逻辑。ACM 输入读取超时字符串长度很大 (10^5)使用未优化的cin/cout。检查题目给出的时间限制和字符串长度。C 中使用ios::sync_with_stdio(false); cin.tie(0);或改用scanf/printf。内存超限1. 使用了不必要的全局大数组。2. 存储了所有子串的哈希值而非前缀哈希。检查数组大小是否与题目最大数据范围匹配。1. 使用vector并根据实际输入大小resize。2. 确认算法是O(n)空间而非O(n^2)。输出格式错误多组数据输出时每组结果后是否要换行最后一个结果后是否有空格仔细阅读题目输出说明对比样例输出。严格按照题目要求控制输出格式可以使用cout ans (in-1?\n: )这类技巧。9. 最佳实践与使用建议模板化将调试正确的双哈希和KMP算法封装成类或函数作为你的个人模板库。竞赛时直接套用节省时间减少出错。下标统一在整个解题过程中坚持使用一种下标体系如0-based并在代码注释中明确说明。混乱的下标是万恶之源。测试驱动实现算法后立即用简单、边界、随机的测试用例进行验证。不要等到提交 OJ 才发现问题。理解优于记忆虽然可以背模板但一定要理解next数组的含义和哈希公式的推导。这样在遇到变种题如求最长回文子串、循环节时才能灵活运用。复杂度分析动手编码前先估算时间和空间复杂度确保在题目限制内。例如n10^6时O(n)算法可行O(n^2)绝对不可行。善用 OJ在洛谷、LeetCode 等平台搜索“字符串哈希”、“KMP”相关题目进行专项练习从简单到困难巩固所学。字符串算法是基本功它直接、纯粹不依赖复杂的数学公式但极其考验思维的严谨性和代码的实现能力。把哈希和 KMP 的原理吃透代码写熟你就能解决一大类字符串问题。下次遇到“小明和字符串”、“虚空之花字符串”这类题目时你就能立刻反应出该用哈希快速比较还是用 KMP 寻找模式或是两者结合。从理解原理到默写模板再到解决实际问题每一步都稳扎稳打你的算法竞赛之路会越走越顺。