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

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

## 本节目标

学完后，你能：

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

## 前置知识与课前自测

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

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

<details><summary>答案</summary>

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

</details>

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

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

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

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

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

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

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

<details><summary>展开：失败时手里还握着什么</summary>

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

</details>

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

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

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

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

<details><summary>展开：KMP 从不漏掉当前字符</summary>

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

</details>

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

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

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

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

<details><summary>展开：border 链就是候选清单</summary>

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

</details>

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

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

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

<details><summary>展开：镜像不是猜测，是已知对称的复制</summary>

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

</details>

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

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

<details><summary>展开：两种不同的复用</summary>

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

</details>

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

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

![朴素匹配重复比较的重叠部分](../插图/04-KMP与Manacher/00-字符串-01-KMP重叠.svg)

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

## 步步式引导

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

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

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

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

```text
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$ 的新字符。

![一个已知回文把信息借给镜像中心](../插图/04-KMP与Manacher/00-字符串-02-回文镜像.svg)

```text
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 的半径，却仍可能需要截断。

<details><summary>展开：两个“先借后验”的完整答案</summary>

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

</details>

偶长度回文只需把中心放在两个字符间、调整边界；正式课会统一下标约定。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](../../互动程序/04-KMP与Manacher/00-不从头再看的字符串.py)。选择 `k` 可以看前缀函数构建、失配回跳和朴素比较次数；选择 `m` 可以看每个中心如何借镜像半径再向外扩。

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

## 扩展与联系

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

## 总结与自检

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

<details><summary>自检答案</summary>

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

</details>

## 一周预热安排

- 第 1 天：列出 `ABABA` 的所有 border。
- 第 2 天：手动对 `ABABAC` 做一次 `pi`。
- 第 3 天：画一个回文，给每个中心量奇半径。
- 第 4 天：运行互动程序，比较朴素匹配与 KMP 的字符比较。
- 第 5 天：进入[KMP 正式课](01-KMP失配边界周期与差分建模.md)，之后再读[Manacher 正式课](02-Manacher回文半径与区间计数.md)。