字符串查找算法 · naive matching / KMP / Boyer-Moore / Rabin-Karp
在一段 text 里查找一个 pattern,最朴素的做法是逐位置逐字符比较,一旦失配就退回重来;后续算法的核心都在减少 comparison 次数。从 naive matching 出发,三种经典加速思路各用一招:KMP 靠 prefix function 让文本指针永不回退;Boyer-Moore 从右往左比、用 bad character rule 让窗口大步跳过;Rabin-Karp 把每个窗口压成一个 rolling hash、相等才逐字符确认。每页都能改 text 与 pattern、点单步看对齐网格上的逐格高亮与 comparison 计数。
后半部分换个思路:不再「在线扫一遍」,而是预处理成结构再反复查询。前缀方向——Trie 把一组 word 按公共前缀叠成树,Aho-Corasick 给它加 failure link 一遍命中所有 pattern;后缀方向——suffix array 把 text 的全部后缀排序后二分,suffix tree 把它们叠成一棵可查任意子串的树。其中「NFA、DFA 与子集构造」「suffix automaton」两页会用到有限自动机的基本概念,可先参考 automata 系列。
Naive matching：最直白的对齐与 comparison
把 pattern 对齐到 text 每个位置，从左到右逐字符比；失配就整体右移一格重头再比。单步看对齐网格，统计 comparison 总次数——作为后续算法的对照基准。
KMP：用已匹配的前缀信息省掉回退
先单步看 prefix function / next 数组怎么算出来，再用它驱动匹配：失配时模式指针 j 跳到 prefix[j-1]，而文本指针 i 从不往回走。网格高亮 + prefix 表当前格，直观看懂回退去哪。
Boyer-Moore：从右往左比，大步跳过
每个窗口内从 pattern 右端向左比较，一旦失配就用 bad character rule 把窗口对齐到 pattern 里最后一个该字符，常常一跳跳过一大段 text。看 bad character 表与每次的跳跃距离，并和 naive matching 的 comparison 次数同输入对照。
Rabin-Karp：把窗口压成一个数
用多项式 rolling hash 把每个窗口压成一个数，滑动时 O(1) 更新；哈希相等才逐字符确认。看哈希值随窗口滑动而更新、命中如何触发确认，以及确认步如何抓出 collision / 伪命中。
预处理成结构 · 前缀方向 (多 pattern)
Trie：把一组词按公共前缀叠成树
把多个 word 逐字符插进同一棵树，公共前缀共享同一条路径。看插入动画里节点如何复用或新建，再查询一个串——区分「命中完整 word」「只是前缀」「不在字典」。查询代价只看被查串长度，与字典大小无关。
Aho-Corasick：一遍扫描命中所有 pattern
在 Trie 上给每个节点连 failure link（KMP prefix function 的多模式版），把 text 扫一遍即可命中所有 pattern；再把缺边补全成完全 DFA，让 fail 跳转彻底消失。
预处理成结构 · 后缀方向 (固定 text)
Suffix array：把所有后缀排好序
text 固定、反复查询时，把它的全部后缀按字典序排好。pattern 出现 ⟺ 它是某后缀的前缀，而这些后缀集中在连续一段——于是查询变成一次 binary search。单步看二分如何收窄到命中区间。
Suffix tree：把所有后缀叠成一棵树
把 text 的全部后缀插进一棵 Trie(suffix trie)，再把单链压缩成带子串的边，得到紧凑的 suffix tree。子串查询 = 从 root 沿边走；命中点子树下的叶子就是全部出现位置。与「Trie」那页的前缀树正好镜像对照。
背后的理论 · 自动机视角
NFA、DFA 与子集构造
「KMP」那页的 dfa[c][j] 其实是一台 DFA。本页说明 NFA 是什么、它与 DFA 的差别、二者如何转换：用「子串匹配 NFA」（起点带 Σ 自环、并行尝试每个匹配起点）做子集模拟，再看它经 subset construction 得到的 DFA——正是 KMP 那张表。活跃集合的最大元 = KMP 状态。
Suffix automaton：识别全部子串的最小 DFA
把「suffix tree」那页的「后缀方向」和「自动机」那页的「子集构造」结合起来：一台识别 text 全部子串、状态数 O(n) 的最小 DFA。状态 = endpos 等价类，suffix link 反向连成树。单步看它怎么在线构造——尤其最微妙的分裂 (clone) 那步；再在上面查子串 / 后缀 / 出现次数，并 O(n) 求出本质不同子串总数。
换个问题 · 近似匹配 (编辑距离 / 容错)
编辑距离：把一个词改成另一个最少几步
近似匹配先要定义距离。Levenshtein 编辑距离 = 把 a 改成 b 的最少「插入/删除/替换」步数，用一张动态规划表 dp[i][j] 算。单步填表、看每格在 ↖替换 / ↑删除 / ←插入 三者里取最小，再回溯出具体的编辑操作。它正是「BK-tree」那页使用的距离函数。
BK-tree：在词典里查找编辑距离相近的词
其余各页处理的都是精确匹配；本页处理近似匹配——在词典里找与目标编辑距离 ≤ k 的所有词（拼写纠错 / 模糊搜索 / OCR 后处理）。每个节点存一个词、边权 = 父子的 Levenshtein 距离，查询时靠三角不等式只看 [d-k, d+k] 范围的子树、把其余整片剪掉。单步看插入分桶建树、查询如何一次剪掉一大片不可能的分支。
应用:支撑日常功能的实例
应用实例：敏感词过滤 + 自动补全
两个可交互的真实场景：Aho-Corasick 把上千关键词建成带 fail 指针的 Trie，文本只扫一遍高亮所有命中（敏感词 / 风控 / DPI）;Trie 前缀树输入几个字便弹出候选（搜索框 / 输入法补全）。修改文本 / 词表 / 前缀即时查看效果，再附 ripgrep、BWA 基因比对、BK-tree 纠错等延伸案例。
实际系统中的应用
ripgrep / grep(Boyer-Moore 跳跃)、IDE 全文检索、Elasticsearch / Lucene 倒排索引里的 term 匹配与前缀查询(Trie / FST)。 多模式与安全:防火墙 / 反垃圾 / DLP 用 Aho-Corasick 一遍扫出成百上千个敏感词;Snort / Suricata 的特征匹配。 自动补全与纠错:搜索框 / 输入法的前缀补全用 Trie;拼写纠错、模糊搜索、OCR 后处理用 编辑距离 + BK-tree。 生物信息与压缩:DNA 序列比对的 后缀数组 / FM-index(BWA、Bowtie 基因比对器);bzip2 的 BWT、长文本全文索引也建在后缀结构上。