13.1.4 串
串是由零个或多个字符组成的有限序列。考试中串的概念题不难，真正有区分度的是模式匹配，尤其是普通匹配与 KMP 改进匹配的差别。
基本概念
| 概念 | 含义 |
|---|---|
| 串 | 字符组成的有限序列 |
| 空串 | 长度为 0 的串 |
| 子串 | 串中任意连续字符组成的序列 |
| 主串 | 被匹配的大串 |
| 模式串 | 要在主串中查找的小串 |
| 模式匹配 | 判断模式串是否出现在主串中，并找到位置 |
普通模式匹配 BF
BF 算法用两个下标比较：i 指向主串，j 指向模式串。
mermaid
flowchart TD
A["比较 s[i] 与 t[j]"] --> B{"相等？"}
B -->|是| C["i++，j++"]
C --> D{"j 到达模式串末尾？"}
D -->|是| E["匹配成功"]
D -->|否| A
B -->|否| F["主串回到本轮起点下一位，模式串 j 回到起点"]
F --> A普通匹配的问题在于：一旦中途失败，模式串下标回到起点，主串也要退回到本轮起点的下一位。模式串较长、重复前缀多时，会产生大量重复比较。
KMP 的改进思想
KMP 的核心不是“比较更快”，而是“失败后不让模式串盲目退回开头”。它预先为模式串计算 next 数组，记录每个位置失败时应该回退到哪里。
| 算法 | 失败时怎么退 |
|---|---|
| BF | 模式串回到起点，主串回到本轮起点下一位 |
| KMP | 主串不回退，模式串回到 next[j] 指定的位置 |
课程强调：软考不一定要求完整证明 KMP，但要知道 next 数组的作用和失败回退的特殊点。
next 数组怎么理解
next[j] 记录的是模式串在第 j 个位置失配时，j 应回退到的位置。它只依赖模式串本身，长度与模式串长度一致。
一种常见定义是：
当 next 定义可能略有不同，考试要以题目给出的定义为准。
为什么不同资料的 next 值会不一样
KMP 的版本很多，差异主要来自：
| 差异来源 | 表现 |
|---|---|
| 下标从 0 还是从 1 开始 | next[0] 或 next[1] 初值不同 |
失配后 j 指向哪里 | 有的记录最长相等前后缀长度，有的记录下一次比较位置 |
是否使用改进 nextval | 对重复字符会进一步跳过无效比较 |
因此复习时不要死背某一组数值，要看题目给的递推式和下标约定。
BF 与 KMP 的技术迭代
| 算法 | 优点 | 缺点 | 为什么出现后继改进 |
|---|---|---|---|
| BF | 思路直观，容易实现 | 失配后回退多，最坏复杂度高 | 长文本和重复模式下效率差 |
| KMP | 主串不回退，利用模式串自身规律 | next 数组理解和计算较难 | 用预处理换匹配效率 |
nextval 改进 | 避免部分重复字符导致的无效比较 | 规则更细，考试不一定要求 | 进一步减少回退比较 |
本节例题
KMP 算法中 `next` 数组的主要作用是：
自查清单
- 能否区分主串、模式串和子串？
- 能否画出 BF 算法失配后的回退过程？
- 能否说明 KMP 为什么主串不需要回退？
- 看到
next题时，能否先确认下标从 0 还是从 1 开始？