字符串处理是计算机的日常——搜索、编辑、压缩、拼写检查。本章把字符串问题一网打尽，还顺路教你动态规划（DP）的正确打开方式 🧬。
🔍 字符串匹配：从笨办法到 KMP
问题：在长度 n 的文本 T 里找长度 m 的模式 P。
朴素算法：每个位置都对齐试一遍，最坏 O(n·m)。找 "aaaaab"，每次都要比到最后一刻才发现失败——太惨了 😭。
KMP 算法：核心洞察是——匹配失败时，已经比较过的前缀里藏着可复用的信息，完全不用从头再来。
先对模式 P 预处理出一个失配函数（failure function）：对每个前缀，记录「最长的、既是前缀又是后缀的长度」。匹配时一旦失配，模式串直接滑到这个「部分重叠」处继续，文本指针永不回退。
- 预处理 O(m) + 匹配 O(n) → 总计 O(n + m)，一次都不浪费；
- 例子：P = "ababaca"，在 "abab..." 失配时，前缀 "ab" 恰好可以继续当头用。
Boyer-Moore 更凶残：从右往左比较，失配时按「坏字符」和「好后缀」两条规则大步跳跃，经常一眼都不用看就能跳过一大段——实际文本搜索中最快，浏览器 Ctrl+F 的感觉 🚀。
🗜️ 文本压缩：Huffman 的贪心
每个字符固定 8 bit？浪费！Huffman 编码按出现频率分配变长码：高频字符给短码（如 2 bit），低频字符给长码。
算法：每个字符是一棵单节点树 → 每次取出频率最小的两棵合并 → 循环直到只剩一棵——一个最小堆（第 8 章！积木复用 🧱）搞定。得到的编码是前缀码：任何字符的编码都不是另一个的前缀，解码永不歧义。
「每次都贪当前最优，最后全局也最优」——这就是贪心算法（greedy method），而 Huffman 证明了它对压缩问题确实最优。注意：贪心不是万能的，它成立需要证明 ⚠️。
🌳 Trie：前缀树
Trie（发音 "try"）把每个字符存在树的边上：单词 "cat"、"car"、"cart" 共享 "ca" 前缀路径。
- 查询一个前缀是否存在：O(前缀长度)，与字典多大无关；
- 应用：输入法候选 📱、拼写检查、路由表、自动补全——「按前缀找」的需求全归它。
🧬 动态规划：恐惧退散！
DP 听起来吓人，本质就三句话：
- 把大问题拆成重叠的小问题（比如「前 i 个字符」的最优解）；
- 小问题的答案存进表格（这就是「编程」二字——填表）；
- 每个格子只算一次，把指数级的重复递归压成多项式。
书里的经典例子：最长公共子序列（LCS）。定义 L[i][j] = 两个串的前 i、前 j 个字符的 LCS 长度，然后：
若 T[i-1] == P[j-1]： L[i][j] = L[i-1][j-1] + 1 （匹配，同进）
否则： L[i][j] = max(L[i-1][j], L[i][j-1]) （二选一）
填一张 (n+1)×(m+1) 的表，O(nm) 搞定——对比暴力枚举的指数爆炸，这就是 DP 的威力 💥。填表回溯还能把 LCS 本身打出来。
判断什么时候用 DP：问题有「最优子结构」（大问题最优解包含小问题最优解）+「重叠子问题」（递归会反复算同一小问题）→ 满足就用，两个条件缺一不可。
🎯 本章通关清单
- [ ] 给 "ababaca" 手算失配函数
- [ ] 说明 KMP 为什么文本指针不回退
- [ ] 用优先队列描述 Huffman 建树过程
- [ ] 说出 DP 两要素，并写出 LCS 的状态转移方程
字符串告一段落。下一章是数据结构界的「社交网络」——图算法 🕸️