lessons/课程/04-KMP与Manacher/00-课前零食-不从头再看的字符串.md

课前零食：不从头再看的字符串

字符串算法最容易被误会成“记数组模板”。这节先做两件很人类的事：匹配失败时利用已经看过的文字；找回文时利用已经量过的对称。以后数组名忘了，也能把路重新走出来。

本节目标

学完后，你能：

• 解释朴素匹配为什么会重复比较同一批字符；
• 用 border（既是前缀又是后缀的真子串）推出 KMP 的失配跳转；
• 从逐中心扩展回文，理解 Manacher 为什么能借用镜像半径；
• 分清“最长 border”“匹配长度”和“回文半径”三种相似但不同的量。

前置知识与课前自测

前置：字符串下标、前缀/后缀、循环。尝试：

1. 模式串 AAAA 在文本 AAAAA 中出现几次？
2. ABABA 的最长真前后缀相同部分是什么，长度多少？
3. 以一个字符为中心扩展回文时，左右边界各移动几格？

答案

1. 两次，位置 0 和 1；匹配后清零会漏重叠。2. `ABA`，长度 3。3. 每次同时向外各移动一格，直到越界或两侧字符不同。

互动规则：字符要排队，已经比较过的证据要留档

准备两条纸带：文本 ABABABACABA 与模式 ABABAC。每次比较都在文本和模式下方画一条竖线，并记录 文本位置 i、已连续匹配长度 j、下一次从模式哪一格继续。遇到回文时，改画一条字符串纸带，记录 中心、已确认左右边界、还能免费借到多少对称信息。

本节的互动约束是：每次跳过比较之前，都要写出一份已经成立的证据。若说不出证据，就不能跳。

从零搭框架：先找出哪些字符被白看了

第 0 步：像尺子一样滑动模式串

把模式 ABABAC 从文本第 0 位对齐，逐字符比较。前五位 ABABA 相同，第六位文本是 B、模式是 C，失配。朴素法会把模式右移一格，再从模式第 0 位比起。

停顿 0：失配前已经确认的 ABABA 中，列出所有既是前缀又是后缀的非空字符串。不要只写最长一个。

展开：失败时手里还握着什么

`ABABA` 的 border 有 `A`、`ABA`。这表示刚匹配段的尾部 `ABA` 同时又能充当模式开头；把状态清成 0 会把这份已知相等白白扔掉。

第 1 步：把“已匹配多少”当成唯一状态

先不写数组。令 j 表示“文本当前位置之前，连续匹配了模式前缀的多少字符”。请在这段扫描中填表：

读到的文本字符	读前 j	比较的模式字符	成功/失配	读后 j
A	0
B	1
A	2
B（第一次失配处）	5

停顿 1：失配后如果保留长度 3，下一次为什么应把当前文本字符再与模式第 3 位比较，而不是直接跳到下一个文本字符？

展开：KMP 从不漏掉当前字符

已匹配长度从 5 跳到 `pi[4]=3`，但当前文本的 `B` 还没有和模式第 3 位比较；它可能正好接在 `ABA` 后成为 `ABAB`。KMP 回退的是模式状态 `j`，不是文本指针 `i`，所以不会漏掉重叠匹配。

第 2 步：亲手发明 pi，不要先背下标

对模式 A B A B A C，每写到一个新位置，就问：“当前整个前缀的最长真前缀，也是它的后缀吗？”先写字符串，再写长度：

前缀	所有可用 border	最长长度 pi
A
AB
ABA
ABAB
ABABA
ABABAC

停顿 2：在给 ABABAC 的最后一个 C 求 pi 时，为什么先从长度 3 尝试，而不是从长度 4、2、1 乱猜？

展开：border 链就是候选清单

前五项的 `pi` 是 `0,0,1,2,3`。最后 C 无法接在长度 3 的 border `ABA` 后，于是尝试该 border 的最长 border（长度 1），再失败才归 0。任何更长候选已被失配排除，任何可能更短候选一定在 border 链上；这就是 `j=pi[j-1]` 的来源。

第 3 步：回文也先做暴力，再数重复比较

写 abacaba，对每个位置当中心，左右同时扩。请先填写中心 3（字符 c）能扩到多远，再填写中心 2（字符 a）能扩到多远。然后把中心 3 已经确认的回文区间画成 [0,6]。

停顿 3：中心 4 关于中心 3 的镜像是谁？镜像中心已有半径为什么能先给中心 4 一段免费下界？

展开：镜像不是猜测，是已知对称的复制

中心 4 的镜像是 2。区间 `[0,6]` 已确认回文，镜像中心 2 向左右相等的字符对，映到中心 4 也必相等；只有可能越过右边界 6 的部分需要重新比较。于是状态不是“每个中心独立扩多远”，而是“当前最右已验证回文边界在哪里”。

第 4 步：写出两份框架账本

算法	当前状态	可复用的证据	何时必须做新比较
KMP
Manacher

展开：两种不同的复用

KMP 的状态是已匹配长度 `j`，证据是前缀与后缀相等，只有沿 border 链仍不匹配时才比较；Manacher 的状态包含中心半径与全局 `[L,R]`，证据是已确认回文对称，只有尝试扩出 $R$ 时才比较新字符。它们都不是“不比较”，而是拒绝重复比较已经有证的部分。

问题动机：已经比较过的字，不该再加班

朴素匹配把模式串放在文本每个起点：一旦第 $j$ 位失配，就把模式整体右移一格，再从第 0 位重新比较。若模式是 ABABAC，已经匹配了 ABABA 后失败，前面的 ABA 其实仍可能是下一次匹配的开头；全部扔掉等于让字符白读一遍。

回文也有同一种浪费：逐个中心向两边扩展时，已知一个长回文内部的镜像位置，仍会重新对比很多字符。我们需要给“已经确认的对称”开收据。

步步式引导

1. KMP：失败后能保留多少匹配长度

设已经匹配模式前缀 pattern[0..j-1]。如果下一个字符失配，仍可能成为新开头的部分必须同时：

• 是刚才匹配段的后缀；
• 又是模式串的前缀。

这正是 border。令 pi[i] 是 pattern[0..i] 的最长 border 长度。失配时不试 j-1,j-2,...，而把候选直接跳到 pi[j-1]；若仍失配，再沿 border 链继续跳。

j = 0
for i in 1..len(pattern)-1:
    while j > 0 and pattern[i] != pattern[j]:
        j = pi[j - 1]          # 更短、但仍可能的 border
    if pattern[i] == pattern[j]:
        j += 1
    pi[i] = j

# 扫描文本时用同一段 while；j == len(pattern) 时记录一次匹配

每次 j 回退都严格变小，而每个文本字符只会推动它前进有限次，因此匹配是 $O(n+m)$。KMP 不是“不回退”，而是只回退到有证据的位置。

2. Manacher：镜子先送你一个下界

先只看奇长度回文。radius[i] 表示以 i 为中心、向一侧能扩多远（包含中心，最小为 1）。维护目前最靠右的已知回文区间 $[L,R]$。当新中心 $i\le R$ 时，它关于旧中心的镜像 mirror=L+R-i 已经有半径；radius[i] 至少能取 min(radius[mirror], R-i+1)，然后只检查可能越过 $R$ 的新字符。

L = 0; R = -1
for center in 0..n-1:
    radius[center] = 1 if center > R else min(radius[L + R - center], R - center + 1)
    while characters just outside this radius are equal:
        radius[center] += 1
    if center + radius[center] - 1 > R:
        L = center - radius[center] + 1
        R = center + radius[center] - 1

纸上模拟：先写跳转理由，再允许状态变化

对 KMP，按下表从 ABABA 的失配开始填：

当前 j	已匹配后缀	它是否也是模式前缀	下一候选 j	当前文本字符是否重读
5	ABABA	—
3	ABA	—
1	A	—

对 Manacher，给 abacaba 写出奇半径数组，并圈出哪几个中心位于已有最右区间内。请特别写出中心 5 为什么一开始可借中心 1 的半径，却仍可能需要截断。

展开：两个“先借后验”的完整答案

KMP 从 5 跳到 3，再在当前文本字符上继续比较；若仍失配才跳到 1、0。Manacher 的奇半径为 `[1,2,1,4,1,2,1]`；中心 5 镜像为 1，但可免费使用的半径还受当前右边界限制，实际初值为 `min(radius[1], R-5+1)`。这份 `min` 正是在说“镜像证据不能越过我们尚未验证的边界”。

偶长度回文只需把中心放在两个字符间、调整边界；正式课会统一下标约定。Manacher 快的理由同样不是跳过真相，而是每次额外比较若成功都会把全局右边界推得更远，总推进不超过 $n$。

核心知识：相同的“复用”，不同的证据

KMP 复用的是“前缀和后缀已经相同”的事实；Manacher 复用的是“一个区间已经左右对称”的事实。两者都维护可证明的已知区域，而不是凭感觉跳过字符。

名称	它描述什么	典型下标错误
pi[i]	前缀 0..i 的最长真 border 长度	误把整个串算成 border
j	当前已匹配模式前缀长度	失配后访问 pi[j] 而非 pi[j-1]
radius[i]	中心向外覆盖的半径	把“含中心”与“不含中心”混用

实现指南

• 先决定字符串是 0-based 还是 1-based；KMP 的 j=0 时不能访问 pi[-1]。
• 匹配成功后别直接清零，应令 j=pi[j-1] 才能保留重叠匹配。
• Manacher 的奇、偶半径建议分开数组写，直到你能稳定画出各自覆盖区间。
• Unicode 文本在竞赛里通常不是问题；但若实际按字节处理，别把“字符”与“字节”想成同一个单位。

互动小实验室

运行 不从头再看的字符串.py。选择 k 可以看前缀函数构建、失配回跳和朴素比较次数；选择 m 可以看每个中心如何借镜像半径再向外扩。

先故意把模式换成 AAAA，观察“成功后保留 border”为什么会找到重叠出现。字符没有忘性，只有朴素循环比较健忘。

扩展与联系

Border 链还能找周期、统计前缀出现次数；回文半径还能统计回文子串和回答中心覆盖问题。两者都只适用于比较关系稳定的线性序列；若字符会被中途修改，通常需要不同的数据结构。

总结与自检

1. KMP 失配时为什么 pi[j-1] 是合理的下一候选？
2. Manacher 在 $i\le R$ 时，为什么不能总把镜像半径原封不动抄来？
3. 两个算法各自的全局“不会重复劳动”证据是什么？

自检答案

它是已匹配段最长仍可作新前缀的后缀；镜像回文可能越过当前已确认右界，越界处仍需比较；KMP 的候选沿 border 链减少，Manacher 的额外成功扩展会推进 $R$。

一周预热安排

• 第 1 天：列出 ABABA 的所有 border。
• 第 2 天：手动对 ABABAC 做一次 pi。
• 第 3 天：画一个回文，给每个中心量奇半径。
• 第 4 天：运行互动程序，比较朴素匹配与 KMP 的字符比较。
• 第 5 天：进入KMP 正式课，之后再读Manacher 正式课。