[L2] 60_字符串

核心哲学：在海量字符中建立“结构化索引”。本质是利用前缀复用（前缀函数、KMP、AC）或后缀压缩（SAM、SA）跳过无效比较。

1. 知识图谱与演化

• 核心工具: Fail 指针、后缀排序、状态压缩、回文半径。

• 演化路径:

  1. 前缀结构与单模匹配：前缀函数理论描述 Border 与失配关系，前缀函数题型整理进一步连接 KMP、周期、覆盖与自动机应用。

  2. 多模匹配：AC 自动机，在 Trie 树上构建 Fail 指针。

  3. 后缀结构：SA/SAM，处理子串统计的终极工具。

  4. 回文结构：Manacher/PAM，利用对称性优化。

2. 决策矩阵

• Border、周期与单串匹配：前缀函数理论、前缀函数题型整理。

• 多串匹配 / 关键词统计：[[Note] AC 自动机]。

• 子串出现次数 / 字典序 / 复杂子串结构：[[Note] 结构化索引] (SAM/SA)。

• 最长回文子串 / 回文计数：[[Note] 回文处理] (Manacher/PAM)。

3. 核心板块索引

3.1 [L3] 61 匹配与自动机

• 前缀函数理论：前缀函数、Border 链、周期与 KMP 匹配。

• 前缀函数题型整理：沿 Border 链、字符串覆盖、删除匹配与前缀自动机。

• [[Note] AC 自动机]: 多模式串匹配。

• [[Note] Trie 树]: 字典树基础。

• [[Note] SAM]: (后缀自动机) 子串的最简自动机模型。

3.2 [L3] 62 结构化索引

• [[Note] 后缀数组]: (SA) 后缀排序与 LCP 数组。

• [[Note] 字符串 Hash]: 快速指纹校验。

3.3 [L3] 63 回文处理

• [[Note] Manacher]: 线性最长回文子串。

• [[Note] PAM]: (回文自动机) 回文串的自动机结构。