字符串几乎出现在每一场竞赛编程比赛中，但它绊倒的学生比任何其他主题都多，因为逐个字符比较的朴素解法往往慢得离谱。
当一道题要求你在一段长文本中查找模式、统计重复子串或检测回文时，暴力解法的时间复杂度可能膨胀到 O(n*m)，在大规模输入下超出限制。好消息是，一套精炼且易于理解的竞赛编程字符串算法工具箱就能覆盖绝大多数这类任务。一旦你识别出其中的模式，正确的技术便会一目了然。本指南将带你逐一了解这套工具箱，以及有志的学生该如何为 USACO 等比赛掌握它们。
必须掌握的核心字符串算法
你并不需要几十种技术。深入掌握少数几个可靠的工具，就能让你走得很远：
- 字符串哈希（Rabin-Karp） — 使用滚动哈希以近乎常数的时间把子串当作数字来比较。它与二分查找配合得天衣无缝，适用于查找最长重复子串或最长公共子串等任务。选择合适的底数和较大的模数以避免冲突。
- KMP（Knuth-Morris-Pratt） — 构建一个前缀函数（即 LPS 数组），使模式串永远不会重新扫描已经经过的文本，从而实现确定性的 O(n + m) 匹配。它非常适合流式输入，以及当你想规避哈希冲突这一微小风险的场景。
- Z 算法 — 为每个位置计算从该处出发、与字符串前缀相匹配的最长子串长度。把模式串 + 分隔符 + 文本拼接起来，就能将其转化为干净的线性时间模式匹配，并能优雅地处理重叠匹配。
- 字典树（Trie） — 一种通过共享前缀来存储大量字符串的树，可实现快速查找、自动补全式查询以及按位异或类问题的求解。
- Manacher 算法 — 以线性时间找出以每个位置为中心的最长回文，取代缓慢的回文检测。
对于更难的问题，后缀数组（通常配合 LCP 数组）以及用于一次性匹配多个模式的 Aho-Corasick 自动机变得不可或缺。这些属于进阶内容，因此请等到基础扎实后再学习。
选择合适的工具
把算法与问题对应起来，成功就已经一半了。这里有几条快速的经验法则：
- 在单个文本中查找单个模式？KMP 和 Z 算法都以线性时间运行。挑你写得最有把握的那个。
- 比较大量子串，或需要最长公共/重复子串？哈希配合二分查找通常是最简洁的路径。
- 同时搜索多个模式？在字典树之上构建 Aho-Corasick 自动机。
- 回文密集型问题？选用 Manacher 算法或回文树。
- 子串排序、不同子串计数或后缀比较？带 LCP 的后缀数组是主力工具。
这如何对应到 USACO 等比赛
USA Computing Olympiad 每个赛季举办四场比赛，每场三道题，依据隐藏测试用例评分，并分为四个组别：Bronze、Silver、Gold 和 Platinum。每位新参赛者都从 Bronze 开始，达到每场比赛的晋级分数线即可晋级。字符串题目出现在每个级别：Bronze 和 Silver 的题目倚重细致的操作和简单的匹配，而 Gold 和 Platinum 则可能要求后缀数组、Z 算法或 Aho-Corasick。由于规则和晋级细节会随赛季变化，请始终在 USACO 官方网站上确认当前的赛制和参赛资格，而不要依赖任何单一的指南。
先掌握线性时间的匹配算法；按每小时学习投入来算，它们解锁的题目比任何高级数据结构都多。
一份行之有效的学习计划
一次只学一个算法，并从零开始把它实现出来，然后只用那一个工具解五到十道题，直到它变成本能。保留一份你信赖的个人模板文件。一周之后重温每个主题，以对抗遗忘。在经验丰富的教练反馈下进行有结构的练习，会极大地加速这一过程，这正是有引导的路径往往胜过单打独斗的原因。
相比纯粹的灵光一现，字符串算法更看重模式识别和干净的实现，这使它们成为稳步、可衡量进步的绝佳领域。如果你想要一条从基础到 Platinum 级技术的有结构路径，欢迎了解 BIAA 的竞赛编程课程，在我们的博客上浏览更多学习指南，或今天就从 BIAA 主页开始。