在经历了前三周对基础线性表、二叉树、高级图论与动态规划的深度攻坚后，在过去这一周（W4）的算法体系进阶中，我们全面挺进了算法大厦中拓扑最精妙、应用面极广的高级字符串算法与多模式匹配领域。

从单模式串匹配的暴力优化与 KMP 前缀函数；
到多项式滚动哈希在 $\mathcal{O}(1)$ 常数时间内的子串极速比对；
从字典树（Trie）在前缀补全与 01 二进制异或极值上的贪心应用；
到多模式串匹配巅峰——AC 自动机将 Trie 树与 KMP 失效指针的图论大一统；
直至全串后缀字典序全景排序的终极武器——后缀数组（Suffix Array）与倍增算法。

今天我们把 W4 周字符串全景知识图谱、核心算法选型决策树与工业级模板做一次系统性全景复盘。

W4 字符串算法全景决策树（String Algorithm Decision Tree）

graph TD
    Start[字符串算法问题 / 文本检索业务] --> Goal{匹配目标与场景}

    Goal -->|单模式串快速匹配| SinglePattern{模式串与文本长度特征}
    SinglePattern -->|严格零哈希冲突 / 确定性| KMP[KMP 算法: next 前缀函数 O(N+M)]
    SinglePattern -->|多次提取子串比对 / 快速实现| Hash[多项式双哈希 + Rabin-Karp: O(1) 子串哈希比对]

    Goal -->|海量敏感词多模式匹配 (如 10 万违禁词)| MultiPattern[🔥 AC 自动机 (Aho-Corasick): Trie + Fail 指针 (单遍 O(N) 扫描!)]

    Goal -->|前缀自动补全 / 按位异或最大值| PrefixTree{问题类型}
    PrefixTree -->|单词前缀检索 / 通配符匹配| Trie26[标准 26 叉 Trie 字典树]
    PrefixTree -->|两个数字的最大异或值| Trie01[01-Trie 二进制字典树 (贪心逐位相反匹配)]

    Goal -->|最长重复子串 / 本质不同子串 / LCP| SuffixDomain[🔥 后缀数组 Suffix Array: 倍增排序 + Kasai 引理求 Height]

一、五大核心字符串算法全景对比矩阵

二、核心算法精要心法复盘

1. 多项式双哈希区间提取公式（0922）：

$$\mathbf{\text{Hash}(S[L \dots R]) = \left( H[R] - H[L-1] \times B^{R - L + 1} \right) \pmod M}$$
结合双质数模数（$10^9+7$ 与 $10^9+9$），碰撞概率低于 $10^{-18}$，在 $\mathcal{O}(1)$ 内完成任意子串比对。

2. 01-Trie 最大异或值贪心法则（0923）：

从最高位（第 30 位）向下搜索，遇到当前位 bit，贪心地优先走向相反分支 1 - bit。若存在则累加 ans |= (1 << i)，否则被迫走相同分支。

3. AC 自动机 BFS 构建 Fail 失效指针（0924）：

子节点的 fail 指针指向父节点 fail 对应的子字符节点。通过**字典图优化（Trie Graph）**将空分支直接折叠指向 fail 节点，彻底消灭匹配时的回溯循环。

4. 后缀数组 Kasai 引理（0925）：

$$\mathbf{h[i] \ge h[i-1] - 1}$$
保证计算 Height 数组时公共前缀长度最多减少 1，实现严格 $\mathcal{O}(N)$ 线性构造。

实习生的算法进阶感悟

字符串算法是计算机处理离散符号序列的最高智慧结晶。
从单向扫描到树形分流，从前缀共享到后缀全局排序，算法大师们用严谨的数学构造，将看似杂乱无章的文本流化解为具备高度确定性的高效索引。
搞懂了失效指针、双哈希与后缀倍增，面对任何超大规模文本检索与模式匹配，你都将拥有破局制胜的核心底牌。