朴素法对齐了逐字比，失败就只往右挪一格，前面比过的信息全丢。 KMP 把失败的信息留下来：记住已匹配的前缀，主串指针不回头。 BM 从尾巴开始比，一失败就整段跳过——英文文本上通常是三者里最快的。
前面两节搜的是「一个数在哪儿」，这一节搜的是「一段字在哪儿」。问题形状一样，难度上去了。 三个算法排在一起，正好演示了算法改进的两条路：别丢信息（KMP）、换个方向比（BM）。 这一篇的 next 表是全书第一个「预处理」的例子：先花点时间造一张表，后面每次查都省。
一、朴素：对齐了逐字比
文本是 ABABABCABABABCABABABC，要找 ABABC。
朴素法的做法：把模式串按在文本开头，逐字比；不对就整体往右挪一格，再从头比。
演示里比了 45 次字符，命中三个位置：2、9、16。
「命中三个」这件事值得注意：搜索不只是「有没有」，还要找出全部位置。 朴素法的优点是没有前提、不会错。它的缺点在下面那一句。
二、朴素的问题：失败就退回一格
演示里那句总结很准：这次比到一半失败，下次只往右挪一格，前面比过的信息全丢了。
举个例子：文本是 ABABABC，模式是 ABABC。
前四个字符 ABAB 都匹配上了，第五个字符 C 对 A 失败。
朴素法下一步是把模式串挪一格，从文本的第 2 个字符重新开始比。那四个已经匹配的字符，白比了。
白比四次还不算可怕，可怕的是它每次都白比。 所以最坏情况是「文本长度乘模式长度」——文本一万字、模式一百字，就要比一百万次。 改进的方向已经很清楚了：能不能不白比？
三、KMP：失败的信息别丢
KMP 的思路：既然 ABAB 已经匹配上了，那我就知道文本这一段长什么样——这部分信息不该扔。
它预先算一张 next 表，记的是「这个位置之前，有多大一段前缀和它自己是重复的」。
演示里 ABABC 的 next 表是 0 0 1 2 0。
最后一位前是 ABAB，前缀 AB 和它自己的后两位 AB 重复，所以能省两步。
有了这张表，失败时模式串不是「挪一格」，而是「按表挪到该在的位置」——主串的指针一步都不往回退。 所以 KMP 是线性的：文本每个字符最多看两遍。 演示里 45 次降到 42 次，短文本上看不出优势，文本一长就拉开了。
四、BM：从尾巴开始比
BM 换了个方向：从模式串的最后一个字符开始往前比。 为什么这样更快？ 因为末尾那个字符一旦不匹配，往往能一次跳过好几个字符——它压根不在模式串里，那整段都不用试了。 演示里 BM 只比了 18 次，比朴素法的 45 次少了一半多。
代价是它要维护两张跳转表，实现比 KMP 复杂。这就是「更快」的价钱：预处理更重、代码更难写。
在英文文本上 BM 通常最快，所以 grep 这类工具用的是它的变种（Boyer-Moore-Horspool）。
五、三种放一起
同一段文本、同一个模式，三个算法的结果完全一样，差别全在比了多少次：
| 算法 | 比了几次 | 靠什么省 | 典型用在 |
|---|---|---|---|
| 朴素 | 45 | 不比 | 短文本、偶尔查一次 |
| KMP | 42 | 记住已匹配的前缀 | 文本编辑器、日志过滤 |
| BM | 18 | 从尾部比，失败就整段跳 | grep、搜索框 |
注意「命中位置相同」这一点：三个算法算的是同一个问题的同一个答案，只是走的步数不同。
这就是「同一问题的不同算法」最标准的样子。
演示里那句提醒也要记住：这里文本短，三者数字差得不多；
文本长到几 MB 时，差别会拉到几倍甚至几十倍。
这也是为什么 grep 不满足于朴素法——它每天要在几十 GB 的日志里翻东西，差几倍就是几小时的差别。
六、这三代算法给出两条通用经验
第一条：别丢已经算出来的信息。 KMP 省的就是「白比的那几次」，它把失败变成了有用的线索。 第二条：换个顺序试试。 BM 从尾部比，就多出了一个「整段跳过」的机会。 同一件事的顺序换了，能省的动作就变了。 这两条不只用在字符串搜索。 排序里也能看到影子：归并排序不丢信息（分完的段还有序），希尔排序换顺序（先隔几个比）。
还有一条工程经验：预处理是划算的投资。next 表要花时间算， 但同一段模式要在这段文本里找很多次时，这笔钱早就赚回来了。 这跟 6.1 那条账是同一个道理：先花成本建结构，后面每次查都便宜。
七、动手 Demo：一段文本里找同一段字，三种算法各比多少次
文本是重复三遍的 ABABABC，模式是 ABABC。
先用朴素法逐字比，数清比了多少次、命中在哪几个位置。
再用 KMP（带 next 表）和 BM（从尾部比）各跑一遍，对比次数。
TEXT = 'ABABABCABABABCABABABC'
PAT = 'ABABC'
def naive(t, p):
cnt, hits = 0, []
for i in range(len(t) - len(p) + 1):
for j in range(len(p)):
cnt += 1
if t[i + j] != p[j]:
break
else:
hits.append(i)
return cnt, hits
def build_next(p):
nxt, k = [0] * len(p), 0
for i in range(1, len(p)):
while k and p[i] != p[k]:
k = nxt[k - 1]
if p[i] == p[k]:
k += 1
nxt[i] = k
return nxt
def kmp(t, p):
nxt, cnt, hits, k = build_next(p), 0, [], 0
for i in range(len(t)):
while k and t[i] != p[k]:
k = nxt[k - 1]
cnt += 1
if t[i] == p[k]:
k += 1
if k == len(p):
hits.append(i - k + 1)
k = nxt[k - 1]
return cnt, hits
print('朴素', naive(TEXT, PAT))
print('next', build_next(PAT))
print('KMP ', kmp(TEXT, PAT))
实跑输出：
--------------------------------------------------------------------
字符串搜索：朴素、KMP 与 BM
--------------------------------------------------------------------
① 朴素：对齐了逐字比
--------------------------------------------------------------------
文本：ABABABCABABABCABABABC
要找：ABABC
朴素法比了 45 次字符，命中位置 [2, 9, 16]
朴素法的问题在「退回去重来」：这次比到一半失败，下次只往右挪一格，前面比过的信息全丢了。
② KMP：失败的信息别丢
--------------------------------------------------------------------
next 表：[0, 0, 1, 2, 0]
next 表记的是「这个位置之前，有多大一段前缀和它自己是重复的」。
以 ABABC 为例，最后一位前是 ABAB，前缀 AB 和它自己的后两位 AB 重复，所以能省两步。
KMP 比了 42 次，命中位置 [2, 9, 16]
KMP 的关键是「主串的指针不往回退」。文本每个字符最多看两遍，所以是线性的；
朴素法在最坏情况下是「文本长度 × 模式长度」。
③ BM：从尾巴开始比
--------------------------------------------------------------------
BM 比了 18 次，命中位置 [2, 9, 16]
| 算法 | 比了几次 | 靠什么省 | 典型用在 |
|---|---|---|---|
| 朴素 | 45 | 不比 | 短文本、偶尔查一次 |
| KMP | 42 | 记住已匹配的前缀 | 文本编辑器、日志过滤 |
| BM | 18 | 从尾部比，失败就整段跳 | grep、搜索框 |
三种结果一样（命中位置相同），差别全在比了多少次。
BM 在英文文本上通常最快，因为它一次能跳过好几个字符。
这里文本短，三者数字差得不多。
文本长到几 MB 时，差别会拉到几倍甚至几十倍——这也是为什么 grep 这类工具不满足于朴素法。
①朴素法那个 for ... else 是 Python 的写法：内层循环正常走完（没 break）才执行 else，
也就是「整段都匹配上了」。
②build_next 的 k 是「当前已匹配的前缀长度」，失败时跳到 nxt[k - 1]。这就是 KMP 的全部机制。
③kmp 里 cnt += 1 只数「比较了一次」，主串指针 i 从不减小——这就是「线性」的来源。
④三个结果里命中位置都是 [2, 9, 16]，但比较次数是 45、42、18。
答案一样，代价不同，这就是算法比较的标准姿势。
30 秒实验
- 把模式换成
ABC，看三者次数差多少（越短的模式，差距越小）。 - 把文本重复十遍再跑，看朴素法和 KMP 的差距会不会拉大。
- 打印
build_next对ABAB和AAAA的结果，想想为什么后者全是 1、2、3。
常见误区
- 「KMP 一定比朴素快很多。」短文本上差不了几次，文本长了才拉开。
- 「next 表记的是失败后挪几格。」它记的是「已匹配的前缀有多长」，挪几格是算出来的。
- 「BM 比 KMP 快，所以 KMP 没用。」BM 跳转表更复杂；短模式、流式输入时 KMP 更常被选。
自测三问（点开对答案）
1. 朴素法的问题是什么？ —— 失败后只挪一格，前面已经匹配的信息全丢了，所以最坏是文本长乘模式长。 2. KMP 的 next 表记的是什么？ —— 这个位置之前，模式串有多大一段前缀和它自己的结尾重复。失败时按它跳。 3. BM 为什么能一次跳过好几个字符？ —— 它从模式末尾往前比，末尾字符不在模式里就整段跳过。搜索算法讲完了。 最后一节跳出课本，看一个真实系统：数据库怎么用排序和搜索——顺便实测一下索引到底快多少。
- ☐ （本篇完，下一篇 6.4 数据库里的排序与搜索）