这类 ACM 算法竞赛的课程资料最核心的价值不是罗列知识点而是告诉你哪些是高频考点以及如何把零散的知识点串成能解题的代码。西安交大 ACM 小学期 Day9 的“字符串”专题就是典型例子。它覆盖了从基础操作到哈希、KMP 这些核心算法的完整链路但很多同学学完感觉知识点都会一写题就卡住。问题往往出在几个地方一是对 C 的string和 C 风格字符串混用不熟输入输出格式一换就出错二是哈希只记住了概念没掌握冲突处理和滚动哈希的写法三是 KMP 的next数组背得滚瓜烂熟但遇到变形题就不知道怎么套。这篇文章就围绕这几个实战痛点把 Day9 的内容拆解成能直接用于刷题的思路和代码模板。我会先讲清楚字符串题在竞赛中的常见考法然后重点拆解哈希和 KMP 的落地写法最后给一套从读题到调试的完整避坑指南。如果你正在准备 ACM 或蓝桥杯等比赛或者想系统提升字符串算法的实战能力这篇内容应该能帮你省下不少摸索时间。1. 先厘清竞赛中“字符串”到底考什么别盲目刷题很多人一看到“字符串”就想到各种库函数但 ACM 竞赛环境尤其是 C恰恰限制你直接使用一些高级函数它考察的是底层实现和算法思维。所以第一步不是去背KMP而是先搞清楚比赛里字符串题常见的几种形式。1.1 输入输出格式这是第一道坎竞赛的输入输出和平时写项目完全不同。题目经常给多组测试数据直到文件结束EOF。字符串可能带空格也可能不带。如果你用cin str读带空格的句子第一个空格后的内容就丢了。这就是为什么很多人在“小明和字符串”这类题目上栽跟头。正确的打开方式读不含空格的字符串直接用cin str或scanf(“%s”, char_array)。读含空格的整行包括空格必须用getline(cin, str)。但这里有个巨坑如果前面用了cin n读一个整数cin会留下一个换行符在缓冲区接下来的getline会直接读到空行。解决方法是在cin n后加一句cin.ignore()清空缓冲区。读未知数量的字符串直到 EOF用while(cin str)或while(getline(cin, str))循环。我建议在本地测试时就严格按照 ACM 模式模拟多组数据输入养成习惯。比如把测试用例写在一个input.txt文件里用freopen(“input.txt”, “r”, stdin)重定向输入这样能提前发现格式问题。1.2 字符串的存储与基本操作C string 与 C 风格字符串C 的std::string方便但你要清楚它的复杂度。str ‘a’在尾部追加平均是 O(1)但频繁在头部或中间插入删除可能导致内存重新分配。在数据量极大比如长度超过 1 万时这可能成为性能瓶颈。C 风格字符串char str[]更底层速度快但需要手动管理内存和结束符‘\0’。竞赛中如果题目明确字符串长度固定且较大或者需要极致性能如自己实现哈希用字符数组更稳妥。一个关键对比string比较用,,。char[]比较用strcmp(str1, str2)返回 0 表示相等。string取长度用str.length()或str.size()。char[]取长度用strlen(str)注意这个函数是 O(n) 的别在循环里每次调用。对于“给两个大整数用字符串表示比如 ‘2154365543’, ‘32656442’都可能超过 1 万”这类题目本质是大数运算。用字符串存储数字然后模拟竖式计算。这里考的不是字符串函数而是你对每一位字符转数字c - ‘0’、进位处理、结果反转等细节的掌控。1.3 常见题型分类根据我的经验Day9 覆盖的及相关的字符串题目大致可以归为这几类模拟与处理字符串翻转、替换、分割、大小写转换。例如“字符串字母大小写转换”、“字符串替换”。这类题往往考察对字符 ASCII 码和循环边界的手动处理能力。匹配与查找判断子串、查找模式串出现位置或次数。这是 KMP 和哈希的主战场。计数与统计统计字符出现次数、最长回文子串、不同子串数量等。哈希表unordered_map是利器。大数运算用字符串表示超大整数进行加减乘除。字符串与数值转换如“字符串转数字”要处理正负号、溢出、非法字符。搞清楚题型你才能决定用哪种武器。接下来我们深入最核心的两个武器哈希和 KMP。2. 字符串哈希不只是“映射”关键是“快速比较子串”哈希的概念都知道把字符串映射成一个数字。但竞赛中字符串哈希的核心作用是在 O(1) 时间内判断任意两个子串是否相等。这是暴力比较O(n)无法比拟的。2.1 滚动哈希Rabin-Karp的实现要点我们通常使用多项式哈希把字符串看作一个 P 进制的数对一个模数 M 取余。对于字符串s其哈希值hash(s) (s[0] * P^(n-1) s[1] * P^(n-2) … s[n-1]) % M。为了快速计算任意子串s[l…r]的哈希我们需要预处理前缀哈希定义h[i]为字符串s[0…i-1]的哈希值即前 i 个字符。通常h[0] 0。递推公式h[i] (h[i-1] * P s[i-1]) % M。那么子串s[l…r]0-indexed的哈希值为hash (h[r1] - h[l] * p[r-l1] % M M) % M其中p[i]是预计算的P^i % M。参数选择避坑关键基数 P通常取 131 或 13331这两个是经验值冲突概率较低。模数 M取一个较大的质数如1e97、1e99或者使用双哈希两个模数来进一步降低冲突概率。对于绝大多数竞赛题单哈希用1e97足够。无符号自然溢出另一种更快的写法是使用unsigned long long让计算结果自然溢出相当于对2^64取模。代码更简洁但理论上存在被构造数据冲突的可能。在非极端苛刻的比赛中这也是一种可行选择。2.2 实战代码模板下面是一个使用单哈希模数1e97的 C 模板包含了预处理和子串查询#include iostream #include string #include vector using namespace std; typedef long long ll; const int P 131; // 基数 const int MOD 1e9 7; // 模数 vectorll h, p; // h为前缀哈希数组p为P的幂次数组 // 初始化哈希 void init_hash(const string s) { int n s.length(); h.resize(n 1, 0); p.resize(n 1, 0); p[0] 1; for (int i 1; i n; i) { h[i] (h[i-1] * P s[i-1]) % MOD; p[i] (p[i-1] * P) % MOD; } } // 获取子串 s[l..r] (0-indexed) 的哈希值 ll get_hash(int l, int r) { return (h[r1] - h[l] * p[r-l1] % MOD MOD) % MOD; } int main() { string s “hello world”; init_hash(s); // 比较子串 “hello” 和 “world” ll hash_hello get_hash(0, 4); // “hello” ll hash_world get_hash(6, 10); // “world” if (hash_hello hash_world) { cout “Equal” endl; } else { cout “Not equal” endl; } return 0; }2.3 哈希的应用场景与边界字符串匹配滚动哈希本身就是一个字符串匹配算法Rabin-Karp可以在平均 O(nm) 时间内找到模式串在主串中的所有位置。虽然最坏情况是 O(nm)但竞赛数据很少卡这个。最长回文子串结合二分答案和哈希可以在 O(n log n) 内解决比 Manacher 算法好写。不同子串计数枚举所有子串计算哈希值存入unordered_set集合大小即为答案。注意子串长度可能很大O(n²)需要评估数据范围。判断循环节如果一个长度为 n 的字符串有长度为 len 的循环节那么hash(s[0…n-len-1])应该等于hash(s[len…n-1])。边界提醒哈希值相等不代表字符串绝对相等哈希冲突但在正确参数下概率极低。如果题目非常严谨或你担心就用双哈希。预处理前缀哈希是 O(n) 的之后每次子串比较才是 O(1)。所以它适用于需要频繁比较不同子串的场景。如果只比较一两次直接暴力更简单。3. KMP 算法理解 next 数组的本质而不是背诵KMP 是字符串匹配的经典算法能在 O(nm) 时间内完成匹配。很多人卡在next数组的理解和计算上。3.1 核心思想利用已匹配的信息避免主串指针回退暴力匹配时主串指针 i 和模式串指针 j 匹配失败后i 会回溯到下一个位置j 归零。KMP 的精髓是当s[i] ! p[j]时i 不动j 回溯到next[j]的位置继续尝试匹配。这个next[j]记录了模式串p[0…j-1]这个子串中最长的相等真前缀和真后缀的长度。真前缀/真后缀不包括字符串本身的前缀和后缀。例如 “aba” 的真前缀有 “a”, “ab”真后缀有 “ba”, “a”。最长的相等真前后缀长度是 1“a”。3.2 next 数组的计算关键中的关键next[i]表示模式串p的子串p[0…i-1]的最长相等真前后缀长度。通常next[0] -1或0不同定义代码写法稍有差异。我更喜欢next[0] -1的版本逻辑更清晰。计算next数组的过程可以看作模式串自己与自己进行匹配vectorint getNext(const string p) { int n p.length(); vectorint next(n 1, 0); next[0] -1; int i 0, j -1; while (i n) { if (j -1 || p[i] p[j]) { i; j; next[i] j; // 传统next数组 // 优化版如果 p[i] p[next[i]]可以进一步回溯 // while (j ! -1 p[i] p[j]) j next[j]; // next[i] j; } else { j next[j]; } } return next; }理解这个循环i是后缀的末尾j是前缀的末尾也是next[i]的值。当p[i] p[j]最长相等前后缀长度可以增加 1否则j要回溯到next[j]继续尝试。这个过程和 KMP 匹配主串的过程一模一样。3.3 KMP 匹配过程有了next数组匹配过程就非常直观了int kmp(const string s, const string p) { vectorint next getNext(p); int i 0, j 0; // i主串指针j模式串指针 int n s.length(), m p.length(); while (i n j m) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; } // 如果找到匹配 if (j m) { // 匹配位置是 i - m // 如果要找所有位置这里记录 i - m然后 j next[j] 继续匹配 return i - m; } } return -1; // 未找到 }3.4 KMP 的典型应用与变形标准字符串匹配找模式串在主串中第一次或所有出现的位置。求循环节对于一个长度为 n 的字符串如果n % (n - next[n]) 0那么它存在最小循环节长度为n - next[n]。这是next数组一个非常重要的应用。前后缀问题next数组本身记录了每个位置的最长相等前后缀可以用于解决一些前后缀相关的题目。一个常见误区KMP 的next数组优化版注释掉的那部分是为了避免在形如 “AAAAAB” 匹配 “AAAAC” 时模式串的j多次无意义地回溯。在竞赛中如果模式串重复字符很多使用优化版能提升一些效率但标准版通常也够用。我建议先掌握标准版理解透彻后再看优化。4. 从读题到 AC一套完整的字符串题目处理流程学完算法更重要的是把它们用起来。下面我以一个综合性的思路串联起处理一道字符串题目的全过程。4.1 第一步仔细读题确定输入输出格式和数据范围这是最重要也最容易被忽略的一步。比如题目说“多组数据直到 EOF”你就必须用while(cin str)循环。数据范围决定了你的算法复杂度上限长度 n 1000O(n³) 的暴力可能都行。长度 n 10^5必须 O(n log n) 或 O(n)。长度 n 10^6必须 O(n)且常数要小最好用scanf读入。对于“给两个大整数用字符串表示都可能超过 1 万”这种说明长度 L 可达 10000那么 O(L²) 的算法10^8在 C 中可能卡在时间边缘需要更优的算法或优化常数。4.2 第二步根据问题类型选择核心算法判断子串/查找模式首选 KMP 或字符串哈希。如果只是单次匹配KMP 更标准如果需要频繁比较任意两个子串例如判断一个字符串的多个子串是否相等哈希更优。统计字符/单词出现次数直接用unordered_mapstring, int或unordered_mapchar, int。回文串问题判断整个字符串双指针从两端向中间比较。找最长回文子串Manacher 算法O(n)最专业但不好写。可以用中心扩展法O(n²)应对中等数据或者用哈希二分O(n log n)应对大数据。字符串编辑翻转、替换、分割模拟即可注意下标和边界。大数运算模拟竖式注意进位和结果反转。4.3 第三步编写代码注意细节和调试变量初始化特别是循环中的累加器、结果变量。数组大小开足够大通常比最大数据范围多 10。如果使用 C 风格字符串别忘了给结束符‘\0’留位置。下标问题字符串下标从 0 开始还是从 1 开始next数组长度是 n 还是 n1前后要统一。我推荐在代码开头写清楚索引规则。边界条件空字符串、长度为 1 的字符串、全部相同的字符串如 “aaaa”、模式串比主串长等情况都要测试。输出格式严格按照题目要求注意大小写、空格、换行。4.4 第四步设计测试用例不要只相信样例。自己构造极端情况最小输入空串、单字符。最大输入达到题目给的上限。完全匹配的情况。完全不匹配的情况。包含特殊字符空格、标点。对于哈希可以尝试构造哈希冲突虽然很难但可以测测不同字符串哈希值是否意外相等。如果题目允许在本地用文件输入输出进行大规模随机测试对比一个暴力但正确的算法比如 O(n²) 匹配和你的优化算法结果是否一致。5. 常见“坑点”与排查清单即使算法原理懂了实现时还是会遇到各种问题。下面是我总结的几个高频“坑点”和排查顺序。5.1 编译与运行时错误“将字符串转换为 uniqueidentifier 时失败”这类数据库错误在 ACM 题中不常见但如果题目背景涉及数据库可能是字符串格式不符合 GUID/UUID 的格式。竞赛中更可能是一个单纯的字符串解析题让你判断格式是否正确。“有 xml 错误的 /xl/sharedStrings.xml。(字符串) 字符非法”这看起来像处理 Excel 文件时的错误。如果题目是字符串处理可能是输入中包含了不可见字符或非法 XML 字符。用isprint()函数检查或直接忽略非字母数字字符。“录入数据库 字符串变成??”这是字符编码问题如 UTF-8 和 GBK 不匹配。在纯算法竞赛中输入通常是 ASCII 或可见字符很少遇到。如果遇到可以尝试用cin按字节读入后过滤。数组越界这是最最常见的运行时错误如 Segmentation Fault。检查循环条件是否可能访问str[str.length()]记住合法下标是0到length()-1。next数组、h数组、p数组的大小是否足够通常是n5或n10。使用scanf(“%s”, str)时str数组是否足够大。5.2 逻辑错误代码能跑但答案不对哈希值计算错误检查P和MOD的值是否写错。检查前缀哈希递推公式h[i] (h[i-1] * P s[i-1]) % MOD。注意是s[i-1]因为h[i]对应前 i 个字符。检查子串哈希公式(h[r1] - h[l] * p[r-l1] % MOD MOD) % MOD。确保p数组正确预计算。对于自然溢出法使用unsigned long long并确保乘法不会提前溢出可能需要强制类型转换。KMP 的 next 数组错误打印出你计算的next数组和手算结果对比。对于模式串 “abababc”next数组从 0 开始next[0]-1应该是[-1, 0, 0, 1, 2, 3, 4, 0]长度 n1。匹配失败时j next[j]而不是j 0。找到一次匹配后如果要继续找j应该重置为next[j]而不是 0。输入输出格式错误多组数据没清空上一个案例的变量或容器。输出忘了换行或者多了空格。用getline读入时没处理掉之前的换行符。5.3 性能问题超时 TLE复杂度估计错误O(n²) 的算法处理 10^5 的数据肯定会超时。重新评估数据范围。在循环内调用 strlen() 或str.length()这两个函数复杂度是 O(n)。如果字符串长度不变应该在循环外先存到变量里。不必要的拷贝频繁使用substr会生成新的字符串对象开销大。在可能的情况下使用索引或引用。哈希冲突导致退化为 O(n)如果使用哈希且发生大量冲突查找会退化为链表 O(n)。考虑换用双哈希或调整参数。Cendl刷新缓冲区在输出大量数据时用‘\n’代替endl因为endl会强制刷新输出流很慢。6. 如何有效练习与提升最后给一个切实可行的练习路径把 Day9 的知识点转化成实战能力。6.1 分阶段刷题第一阶段基础操作与模拟题目字符串翻转、替换、分割、统计字符出现次数。目标熟悉string和char[]的基本操作熟练处理输入输出。建议题量5-10 题。第二阶段哈希专题题目使用哈希解决字符串匹配、最长回文子串、不同子串计数等问题。目标能独立写出滚动哈希的预处理和查询函数理解双哈希的原理。建议题量5-8 题。第三阶段KMP 专题题目标准字符串匹配、求循环节、前后缀相关问题。目标能默写getNext和kmpMatch函数理解next数组的每个值含义。建议题量5-8 题。第四阶段综合应用题目结合哈希、KMP、动态规划、贪心等算法的字符串综合题。目标能准确分析问题选择合适算法处理边界条件。建议题量8-12 题。6.2 建立自己的代码模板库将验证过的、无 bug 的代码保存为模板滚动哈希单哈希/双哈希模板。KMP标准版/优化版模板。读入多组字符串数据的模板处理cin与getline混用。大数加法/减法的模板。比赛时直接复制粘贴能节省大量时间减少低级错误。6.3 模拟赛环境训练在 OJOnline Judge上做题时刻意模拟比赛环境关闭代码自动补全和语法高亮如果可能。严格限制时间如单题 30 分钟。从零开始写代码而不是在原有代码上修改。写完代码后先静态检查再用小样例测试最后用自造的大数据和极端数据测试。字符串题目往往代码不长但细节致命。一个下标错误就能让你调试半小时。最好的方法就是前期通过足够多的练习把常见的坑都踩一遍形成肌肉记忆和条件反射。当你拿到新题能立刻想到“这题可能考哈希冲突”或者“那个边界需要特判”时Day9 的内容才算真正内化成了你的解题能力。
这类 ACM 算法竞赛的课程资料最核心的价值不是罗列知识点而是告诉你哪些是高频考点以及如何把零散的知识点串成能解题的代码。西安交大 ACM 小学期 Day9 的“字符串”专题就是典型例子。它覆盖了从基础操作到哈希、KMP 这些核心算法的完整链路但很多同学学完感觉知识点都会一写题就卡住。问题往往出在几个地方一是对 C 的string和 C 风格字符串混用不熟输入输出格式一换就出错二是哈希只记住了概念没掌握冲突处理和滚动哈希的写法三是 KMP 的next数组背得滚瓜烂熟但遇到变形题就不知道怎么套。这篇文章就围绕这几个实战痛点把 Day9 的内容拆解成能直接用于刷题的思路和代码模板。我会先讲清楚字符串题在竞赛中的常见考法然后重点拆解哈希和 KMP 的落地写法最后给一套从读题到调试的完整避坑指南。如果你正在准备 ACM 或蓝桥杯等比赛或者想系统提升字符串算法的实战能力这篇内容应该能帮你省下不少摸索时间。1. 先厘清竞赛中“字符串”到底考什么别盲目刷题很多人一看到“字符串”就想到各种库函数但 ACM 竞赛环境尤其是 C恰恰限制你直接使用一些高级函数它考察的是底层实现和算法思维。所以第一步不是去背KMP而是先搞清楚比赛里字符串题常见的几种形式。1.1 输入输出格式这是第一道坎竞赛的输入输出和平时写项目完全不同。题目经常给多组测试数据直到文件结束EOF。字符串可能带空格也可能不带。如果你用cin str读带空格的句子第一个空格后的内容就丢了。这就是为什么很多人在“小明和字符串”这类题目上栽跟头。正确的打开方式读不含空格的字符串直接用cin str或scanf(“%s”, char_array)。读含空格的整行包括空格必须用getline(cin, str)。但这里有个巨坑如果前面用了cin n读一个整数cin会留下一个换行符在缓冲区接下来的getline会直接读到空行。解决方法是在cin n后加一句cin.ignore()清空缓冲区。读未知数量的字符串直到 EOF用while(cin str)或while(getline(cin, str))循环。我建议在本地测试时就严格按照 ACM 模式模拟多组数据输入养成习惯。比如把测试用例写在一个input.txt文件里用freopen(“input.txt”, “r”, stdin)重定向输入这样能提前发现格式问题。1.2 字符串的存储与基本操作C string 与 C 风格字符串C 的std::string方便但你要清楚它的复杂度。str ‘a’在尾部追加平均是 O(1)但频繁在头部或中间插入删除可能导致内存重新分配。在数据量极大比如长度超过 1 万时这可能成为性能瓶颈。C 风格字符串char str[]更底层速度快但需要手动管理内存和结束符‘\0’。竞赛中如果题目明确字符串长度固定且较大或者需要极致性能如自己实现哈希用字符数组更稳妥。一个关键对比string比较用,,。char[]比较用strcmp(str1, str2)返回 0 表示相等。string取长度用str.length()或str.size()。char[]取长度用strlen(str)注意这个函数是 O(n) 的别在循环里每次调用。对于“给两个大整数用字符串表示比如 ‘2154365543’, ‘32656442’都可能超过 1 万”这类题目本质是大数运算。用字符串存储数字然后模拟竖式计算。这里考的不是字符串函数而是你对每一位字符转数字c - ‘0’、进位处理、结果反转等细节的掌控。1.3 常见题型分类根据我的经验Day9 覆盖的及相关的字符串题目大致可以归为这几类模拟与处理字符串翻转、替换、分割、大小写转换。例如“字符串字母大小写转换”、“字符串替换”。这类题往往考察对字符 ASCII 码和循环边界的手动处理能力。匹配与查找判断子串、查找模式串出现位置或次数。这是 KMP 和哈希的主战场。计数与统计统计字符出现次数、最长回文子串、不同子串数量等。哈希表unordered_map是利器。大数运算用字符串表示超大整数进行加减乘除。字符串与数值转换如“字符串转数字”要处理正负号、溢出、非法字符。搞清楚题型你才能决定用哪种武器。接下来我们深入最核心的两个武器哈希和 KMP。2. 字符串哈希不只是“映射”关键是“快速比较子串”哈希的概念都知道把字符串映射成一个数字。但竞赛中字符串哈希的核心作用是在 O(1) 时间内判断任意两个子串是否相等。这是暴力比较O(n)无法比拟的。2.1 滚动哈希Rabin-Karp的实现要点我们通常使用多项式哈希把字符串看作一个 P 进制的数对一个模数 M 取余。对于字符串s其哈希值hash(s) (s[0] * P^(n-1) s[1] * P^(n-2) … s[n-1]) % M。为了快速计算任意子串s[l…r]的哈希我们需要预处理前缀哈希定义h[i]为字符串s[0…i-1]的哈希值即前 i 个字符。通常h[0] 0。递推公式h[i] (h[i-1] * P s[i-1]) % M。那么子串s[l…r]0-indexed的哈希值为hash (h[r1] - h[l] * p[r-l1] % M M) % M其中p[i]是预计算的P^i % M。参数选择避坑关键基数 P通常取 131 或 13331这两个是经验值冲突概率较低。模数 M取一个较大的质数如1e97、1e99或者使用双哈希两个模数来进一步降低冲突概率。对于绝大多数竞赛题单哈希用1e97足够。无符号自然溢出另一种更快的写法是使用unsigned long long让计算结果自然溢出相当于对2^64取模。代码更简洁但理论上存在被构造数据冲突的可能。在非极端苛刻的比赛中这也是一种可行选择。2.2 实战代码模板下面是一个使用单哈希模数1e97的 C 模板包含了预处理和子串查询#include iostream #include string #include vector using namespace std; typedef long long ll; const int P 131; // 基数 const int MOD 1e9 7; // 模数 vectorll h, p; // h为前缀哈希数组p为P的幂次数组 // 初始化哈希 void init_hash(const string s) { int n s.length(); h.resize(n 1, 0); p.resize(n 1, 0); p[0] 1; for (int i 1; i n; i) { h[i] (h[i-1] * P s[i-1]) % MOD; p[i] (p[i-1] * P) % MOD; } } // 获取子串 s[l..r] (0-indexed) 的哈希值 ll get_hash(int l, int r) { return (h[r1] - h[l] * p[r-l1] % MOD MOD) % MOD; } int main() { string s “hello world”; init_hash(s); // 比较子串 “hello” 和 “world” ll hash_hello get_hash(0, 4); // “hello” ll hash_world get_hash(6, 10); // “world” if (hash_hello hash_world) { cout “Equal” endl; } else { cout “Not equal” endl; } return 0; }2.3 哈希的应用场景与边界字符串匹配滚动哈希本身就是一个字符串匹配算法Rabin-Karp可以在平均 O(nm) 时间内找到模式串在主串中的所有位置。虽然最坏情况是 O(nm)但竞赛数据很少卡这个。最长回文子串结合二分答案和哈希可以在 O(n log n) 内解决比 Manacher 算法好写。不同子串计数枚举所有子串计算哈希值存入unordered_set集合大小即为答案。注意子串长度可能很大O(n²)需要评估数据范围。判断循环节如果一个长度为 n 的字符串有长度为 len 的循环节那么hash(s[0…n-len-1])应该等于hash(s[len…n-1])。边界提醒哈希值相等不代表字符串绝对相等哈希冲突但在正确参数下概率极低。如果题目非常严谨或你担心就用双哈希。预处理前缀哈希是 O(n) 的之后每次子串比较才是 O(1)。所以它适用于需要频繁比较不同子串的场景。如果只比较一两次直接暴力更简单。3. KMP 算法理解 next 数组的本质而不是背诵KMP 是字符串匹配的经典算法能在 O(nm) 时间内完成匹配。很多人卡在next数组的理解和计算上。3.1 核心思想利用已匹配的信息避免主串指针回退暴力匹配时主串指针 i 和模式串指针 j 匹配失败后i 会回溯到下一个位置j 归零。KMP 的精髓是当s[i] ! p[j]时i 不动j 回溯到next[j]的位置继续尝试匹配。这个next[j]记录了模式串p[0…j-1]这个子串中最长的相等真前缀和真后缀的长度。真前缀/真后缀不包括字符串本身的前缀和后缀。例如 “aba” 的真前缀有 “a”, “ab”真后缀有 “ba”, “a”。最长的相等真前后缀长度是 1“a”。3.2 next 数组的计算关键中的关键next[i]表示模式串p的子串p[0…i-1]的最长相等真前后缀长度。通常next[0] -1或0不同定义代码写法稍有差异。我更喜欢next[0] -1的版本逻辑更清晰。计算next数组的过程可以看作模式串自己与自己进行匹配vectorint getNext(const string p) { int n p.length(); vectorint next(n 1, 0); next[0] -1; int i 0, j -1; while (i n) { if (j -1 || p[i] p[j]) { i; j; next[i] j; // 传统next数组 // 优化版如果 p[i] p[next[i]]可以进一步回溯 // while (j ! -1 p[i] p[j]) j next[j]; // next[i] j; } else { j next[j]; } } return next; }理解这个循环i是后缀的末尾j是前缀的末尾也是next[i]的值。当p[i] p[j]最长相等前后缀长度可以增加 1否则j要回溯到next[j]继续尝试。这个过程和 KMP 匹配主串的过程一模一样。3.3 KMP 匹配过程有了next数组匹配过程就非常直观了int kmp(const string s, const string p) { vectorint next getNext(p); int i 0, j 0; // i主串指针j模式串指针 int n s.length(), m p.length(); while (i n j m) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; } // 如果找到匹配 if (j m) { // 匹配位置是 i - m // 如果要找所有位置这里记录 i - m然后 j next[j] 继续匹配 return i - m; } } return -1; // 未找到 }3.4 KMP 的典型应用与变形标准字符串匹配找模式串在主串中第一次或所有出现的位置。求循环节对于一个长度为 n 的字符串如果n % (n - next[n]) 0那么它存在最小循环节长度为n - next[n]。这是next数组一个非常重要的应用。前后缀问题next数组本身记录了每个位置的最长相等前后缀可以用于解决一些前后缀相关的题目。一个常见误区KMP 的next数组优化版注释掉的那部分是为了避免在形如 “AAAAAB” 匹配 “AAAAC” 时模式串的j多次无意义地回溯。在竞赛中如果模式串重复字符很多使用优化版能提升一些效率但标准版通常也够用。我建议先掌握标准版理解透彻后再看优化。4. 从读题到 AC一套完整的字符串题目处理流程学完算法更重要的是把它们用起来。下面我以一个综合性的思路串联起处理一道字符串题目的全过程。4.1 第一步仔细读题确定输入输出格式和数据范围这是最重要也最容易被忽略的一步。比如题目说“多组数据直到 EOF”你就必须用while(cin str)循环。数据范围决定了你的算法复杂度上限长度 n 1000O(n³) 的暴力可能都行。长度 n 10^5必须 O(n log n) 或 O(n)。长度 n 10^6必须 O(n)且常数要小最好用scanf读入。对于“给两个大整数用字符串表示都可能超过 1 万”这种说明长度 L 可达 10000那么 O(L²) 的算法10^8在 C 中可能卡在时间边缘需要更优的算法或优化常数。4.2 第二步根据问题类型选择核心算法判断子串/查找模式首选 KMP 或字符串哈希。如果只是单次匹配KMP 更标准如果需要频繁比较任意两个子串例如判断一个字符串的多个子串是否相等哈希更优。统计字符/单词出现次数直接用unordered_mapstring, int或unordered_mapchar, int。回文串问题判断整个字符串双指针从两端向中间比较。找最长回文子串Manacher 算法O(n)最专业但不好写。可以用中心扩展法O(n²)应对中等数据或者用哈希二分O(n log n)应对大数据。字符串编辑翻转、替换、分割模拟即可注意下标和边界。大数运算模拟竖式注意进位和结果反转。4.3 第三步编写代码注意细节和调试变量初始化特别是循环中的累加器、结果变量。数组大小开足够大通常比最大数据范围多 10。如果使用 C 风格字符串别忘了给结束符‘\0’留位置。下标问题字符串下标从 0 开始还是从 1 开始next数组长度是 n 还是 n1前后要统一。我推荐在代码开头写清楚索引规则。边界条件空字符串、长度为 1 的字符串、全部相同的字符串如 “aaaa”、模式串比主串长等情况都要测试。输出格式严格按照题目要求注意大小写、空格、换行。4.4 第四步设计测试用例不要只相信样例。自己构造极端情况最小输入空串、单字符。最大输入达到题目给的上限。完全匹配的情况。完全不匹配的情况。包含特殊字符空格、标点。对于哈希可以尝试构造哈希冲突虽然很难但可以测测不同字符串哈希值是否意外相等。如果题目允许在本地用文件输入输出进行大规模随机测试对比一个暴力但正确的算法比如 O(n²) 匹配和你的优化算法结果是否一致。5. 常见“坑点”与排查清单即使算法原理懂了实现时还是会遇到各种问题。下面是我总结的几个高频“坑点”和排查顺序。5.1 编译与运行时错误“将字符串转换为 uniqueidentifier 时失败”这类数据库错误在 ACM 题中不常见但如果题目背景涉及数据库可能是字符串格式不符合 GUID/UUID 的格式。竞赛中更可能是一个单纯的字符串解析题让你判断格式是否正确。“有 xml 错误的 /xl/sharedStrings.xml。(字符串) 字符非法”这看起来像处理 Excel 文件时的错误。如果题目是字符串处理可能是输入中包含了不可见字符或非法 XML 字符。用isprint()函数检查或直接忽略非字母数字字符。“录入数据库 字符串变成??”这是字符编码问题如 UTF-8 和 GBK 不匹配。在纯算法竞赛中输入通常是 ASCII 或可见字符很少遇到。如果遇到可以尝试用cin按字节读入后过滤。数组越界这是最最常见的运行时错误如 Segmentation Fault。检查循环条件是否可能访问str[str.length()]记住合法下标是0到length()-1。next数组、h数组、p数组的大小是否足够通常是n5或n10。使用scanf(“%s”, str)时str数组是否足够大。5.2 逻辑错误代码能跑但答案不对哈希值计算错误检查P和MOD的值是否写错。检查前缀哈希递推公式h[i] (h[i-1] * P s[i-1]) % MOD。注意是s[i-1]因为h[i]对应前 i 个字符。检查子串哈希公式(h[r1] - h[l] * p[r-l1] % MOD MOD) % MOD。确保p数组正确预计算。对于自然溢出法使用unsigned long long并确保乘法不会提前溢出可能需要强制类型转换。KMP 的 next 数组错误打印出你计算的next数组和手算结果对比。对于模式串 “abababc”next数组从 0 开始next[0]-1应该是[-1, 0, 0, 1, 2, 3, 4, 0]长度 n1。匹配失败时j next[j]而不是j 0。找到一次匹配后如果要继续找j应该重置为next[j]而不是 0。输入输出格式错误多组数据没清空上一个案例的变量或容器。输出忘了换行或者多了空格。用getline读入时没处理掉之前的换行符。5.3 性能问题超时 TLE复杂度估计错误O(n²) 的算法处理 10^5 的数据肯定会超时。重新评估数据范围。在循环内调用 strlen() 或str.length()这两个函数复杂度是 O(n)。如果字符串长度不变应该在循环外先存到变量里。不必要的拷贝频繁使用substr会生成新的字符串对象开销大。在可能的情况下使用索引或引用。哈希冲突导致退化为 O(n)如果使用哈希且发生大量冲突查找会退化为链表 O(n)。考虑换用双哈希或调整参数。Cendl刷新缓冲区在输出大量数据时用‘\n’代替endl因为endl会强制刷新输出流很慢。6. 如何有效练习与提升最后给一个切实可行的练习路径把 Day9 的知识点转化成实战能力。6.1 分阶段刷题第一阶段基础操作与模拟题目字符串翻转、替换、分割、统计字符出现次数。目标熟悉string和char[]的基本操作熟练处理输入输出。建议题量5-10 题。第二阶段哈希专题题目使用哈希解决字符串匹配、最长回文子串、不同子串计数等问题。目标能独立写出滚动哈希的预处理和查询函数理解双哈希的原理。建议题量5-8 题。第三阶段KMP 专题题目标准字符串匹配、求循环节、前后缀相关问题。目标能默写getNext和kmpMatch函数理解next数组的每个值含义。建议题量5-8 题。第四阶段综合应用题目结合哈希、KMP、动态规划、贪心等算法的字符串综合题。目标能准确分析问题选择合适算法处理边界条件。建议题量8-12 题。6.2 建立自己的代码模板库将验证过的、无 bug 的代码保存为模板滚动哈希单哈希/双哈希模板。KMP标准版/优化版模板。读入多组字符串数据的模板处理cin与getline混用。大数加法/减法的模板。比赛时直接复制粘贴能节省大量时间减少低级错误。6.3 模拟赛环境训练在 OJOnline Judge上做题时刻意模拟比赛环境关闭代码自动补全和语法高亮如果可能。严格限制时间如单题 30 分钟。从零开始写代码而不是在原有代码上修改。写完代码后先静态检查再用小样例测试最后用自造的大数据和极端数据测试。字符串题目往往代码不长但细节致命。一个下标错误就能让你调试半小时。最好的方法就是前期通过足够多的练习把常见的坑都踩一遍形成肌肉记忆和条件反射。当你拿到新题能立刻想到“这题可能考哈希冲突”或者“那个边界需要特判”时Day9 的内容才算真正内化成了你的解题能力。
![[论文分析]ZeroDayBench：面向网络防御的未知零日漏洞LLM智能体评估](http://pic.xiahunao.cn/yaotu/[论文分析]ZeroDayBench：面向网络防御的未知零日漏洞LLM智能体评估)
![[论文分析]CyberSleuth：自主蓝队LLM智能体用于Web攻击取证的深度分析](http://pic.xiahunao.cn/yaotu/[论文分析]CyberSleuth：自主蓝队LLM智能体用于Web攻击取证的深度分析)
