字符串算法：从匹配到结构

字符串是计算机科学中最基本的数据类型之一。在算法竞赛与工程应用中，高效处理字符串的匹配、回文性质、子串分布以及复杂结构提取是核心能力。本章节将从最基础的模式匹配出发，逐步深入到自动机理论、周期性边界分析与后缀结构。

核心知识板块

单模式匹配与周期理论

从 $O(nm)$ 的暴力匹配到 $O(n)$ 的 KMP 算法，深入理解前缀函数、势能分析以及 Weak Periodicity Lemma。

回文性质分析

利用回文串的对称性，Manacher 算法可以在线性时间内提取所有最长回文子串，掌握回文半径与对称中心的关系。

哈希与随机化分析

字符串哈希是 $O(1)$ 判定子串相等的利器，理解生日悖论下的碰撞概率评估与双哈希防御策略。

多模式匹配自动机

AC 自动机将 Trie 树与 KMP 思想结合，构建出处理多模式匹配的高效 DFA，掌握 Fail 树拓扑优化。

后缀结构：子串性质的终极武器

后缀自动机 (SAM) 与后缀数组 (SA) 是处理字符串子串性质的巅峰。它们能够在线性或线性对数时间内完成子串统计、最长公共子串、不同子串个数等复杂任务，深度掌握 Endpos 等价类 与 Parent Tree 理论。

探索后缀结构

本板块不仅关注算法实现，更强调其背后的数学逻辑：

算法竞赛习题库：字符串算法专题

包含 KMP、Manacher、AC 自动机与后缀自动机 (SAM) 阶梯练习，所有题目均配有 C++ 详细解析。