字符串算法可视化
子串搜索遇到失配时，朴素方法把模式移一位再重试。更好的方法会保存可复用信息：模式的前后缀关系、当前窗口的哈希，或为后续多次查询建立的索引。
KMP 利用已匹配后缀也是模式前缀的性质，让文本指针不后退。Rabin-Karp 保存窗口指纹，移动时更新。后缀数组先排序每个后缀的起始位置，之后用二分回答子串查询。
三种复用方式
| 算法 | 保存的状态 | 预处理 | 一次查询 |
|---|---|---|---|
| KMP | LPS 表中的相同前后缀长度 | O(m) | O(n + m) |
| Rabin-Karp | 模式与窗口的指纹 | O(m) | 期望 O(n + m)，最坏 O(nm) |
| 后缀数组 | 按字典序排列的后缀起点 | 本课 O(n log^2 n) | O(m log n) |
KMP 针对模式预处理，提供确定性的线性上界。Rabin-Karp 展示窗口复用，但哈希相等仍需逐字符确认。后缀数组准备成本更高，适合同一文本接收多次查询。
建议学习顺序
先学 KMP。LPS 表说明失配后可以保留哪段已匹配内容。观察文本指针不动，模式匹配长度回退。错误版本在这一刻推进文本指针，因此漏掉真实匹配。
再学 Rabin-Karp。固定宽度窗口每次移动一位，滚动公式移除离开的数字、加入新数字，无需重读中间部分。默认例子中，31428 与 31415 模 13 的哈希相同，字符校验会拒绝前者。
最后学后缀数组。BANANA 的重复前缀展示排序难点，倍增法把比较变成整数秩对。后缀起点排好序后，用 lower-bound 二分查找 ANA。
观察重点
- KMP 保留的匹配长度与模式移动距离相关，但不是同一个量。
- Rabin-Karp 的模式行消失时，表示哈希不同，该窗口可跳过全部字符比较。
- 后缀数组用
-1标记结尾，让其他前缀相同时A排在ANA之前。 - 对照失败例，检查改错一行或破坏前提后，复用规则为何不再成立。
全部字符串算法可视化课程
改变输入，逐步查看轨迹，并对照 Python 或 JavaScript 代码。