---
title: "04-串与KMP"
created: 2026-08-29
tags:
  - 基础与理论
  - 数据结构
  - "408"
---

# 04 串与KMP

> 📚 本文是 [[00-数据结构总览|数据结构]] 的第 4 篇，相关系列见 [[00-基础与理论|基础与理论]]。

串（字符串）= 内容受限的线性表，元素只能字符。它独立成章只为一件事：**KMP 模式匹配算法**——408 数据结构里最"硬"的算法，考 next 数组的手算，一算错整题全错。本篇用最直白的推导把 next 讲到"考场能手写"。

## 一、串的基本盘

- **空串 vs 空格串**：空串长度 0；空格串是"若干空格"，长度 ≠ 0
- **子串**：串中任意连续字符组成的子序列；**真子串** ≠ 本身
- **子串位置** = 子串第一个字符在主串中的**位序**（从 1 起，王道约定）
- 串相等 = 长度相等 **且** 对应位置字符都相等
- 存储：定长顺序存储 / 堆分配（动态）/ 块链存储（每结点存多个字符——省指针开销）

⚠️ C 语言的 `strlen` 是 O(n)（数到 `\0`）；Java/Python 的 length 是 O(1)（对象头记着）——[[05-字符编码|字符编码]]里"UTF-16 代理对"坑也在这层。

## 二、朴素匹配：暴力够用吗

主串 S 长 n，模式串 P 长 m。朴素匹配：从主串每个位置起，与 P 逐位比较，失败就把主串指针**回退一位**重来。

```
S: a b c a b d ...
P: a b c a b e     第 6 位失配
朴素：主串指针退回第 2 位，P 指针回 1，重来
```

- 最好 O(n)，最坏 **O(n·m)**（如 S="aaaa…ab"、P="aaab"）
- 每次失配都"全盘重来"，浪费了**已经比较过的信息**——KMP 的全部灵感就在这：**失配时，主串指针不回退，只滑动模式串**。

## 三、KMP 的核心直觉

失配时，前面已经匹配的那段（P 的前缀）是**已知**的。问：**已匹配前缀里，有没有"既是前缀又是后缀"的部分，可以直接对上主串的尾部？**

```
S: a b c a b d
P: a b c a b e      失配在 e（P[6]）
已匹配段 "abcab" 的最长相等前后缀 = "ab"（长度 2）
→ P 右滑，让 P 的前缀 "ab" 直接对上主串已比过的 "ab"：
S: a b c a b d
P:       a b c ...   ← 主串指针不动，P 指针跳到第 3 位继续
```

**next 数组就是"每个位置失配后，P 指针跳到哪"的查表**。

## 四、next 手算（408 考场流程）

**王道 1-based 约定**：`next[j]` = "P[1..j−1] 这段（不含当前失配位）的**最长相等前后缀长度 + 1**"，且 **next[1] = 0**（第一位失配，无路可退，主串前进 P 重来）。

**手算流程（背这个）**：对每个位置 j，看 P[1..j−1] 的"真前缀 == 真后缀"最长长度 L，则 next[j] = L + 1。

**例题：P = "a b c a b"**

| j | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| P[j] | a | b | c | a | b |
| 看 P[1..j−1] | — | "a" | "ab" | "abc" | "abca" |
| 最长相等前后缀 | — | 0 | 0 | 0 | "a"=1 |
| **next[j]** | **0** | **1** | **1** | **1** | **2** |

验证 j=5：前缀 "abca" 中，前缀 "a" == 后缀 "a"（长度 1），"ab" ≠ "ca"，所以 L=1 → next[5]=2 ✅

（再验一个：P="ababaa"，next = 0,1,1,2,3,2——j=6 时 "ababa" 前后缀相等最长 "aba" 长 3 → next[6]=4？注意还要满足"前后缀长度 < j−1"，"aba"=3 < 5 ✅ 所以下一步核对："ababa" 真前后缀：a/a ✅ 1，ab/ba ✗，aba/aba ✅ 3 → L=3 → next[6]=4。但经典答案是 2？——那是 **nextval 或 0-based** 的记法差异！408 王道口径下 next[6]=4。**考场上死守题目给的约定**，0-based 则 next 全体 = 上面 L 值再加偏移，务必先看题干示例。）

### 用 next 匹配（接着上面的例题）

S = "abcabd"，P = "abcab"，next = 0,1,1,1,2：

- 比较 P[1..5] vs S[1..5]：abcab 全对，S[6]=d ≠ P[5]… 等等，P[5]=b 对上了 S[5]=b，失配发生在 P[6]——P 只有 5 位，说明 j=6 越界。换个失配点：S="abcabd"，比到 P[5]=b vs S[5]=b 对上，P[6] 不存在 → 直接匹配成功？不——S 第 6 位是 d，P 已用尽前 5 位且全对 → 匹配成功于位置 1。
- 构造一次真失配：S = "abcacc"，P = "abcab"：P[5]=b vs S[5]=c 失配 → j = next[5] = 2，S 指针不动，从 P[2]=b 与 S[5]=c 继续 → 失配 → j = next[2] = 1 → P[1]=a vs S[5]=c 失配 → j = next[1] = 0 → 主串前进，从 S[6] 与 P[1] 继续。**主串指针从没回退过** ✅

### next 的求法（代码视角，看懂即可）

递推：已知 next[1..j−1]，若 P[j−1] == P[next[j−1]]，则 next[j] = next[j−1] + 1；否则沿着 next 链继续回退。408 主要考手算，代码不默写。

## 五、nextval：next 的升级版

next 有个不彻底之处：跳过去之后的字符**可能还是和失配的那个一样**，白比一次。nextval 在生成 next 时就多问一句：

> nextval[j] = 若 P[next[j]] == P[j]，则直接取 nextval[next[j]]（跳得更远）；否则 = next[j]

- 手算：先算 next，再**从左到右**扫一遍，"跳过去的那个字符和当前字符相同，就继承它的 nextval"
- 效果：匹配仍正确，比较次数更少。408 偶尔考"给 next 求 nextval"，按上面规则逐位继承即可

## 六、复杂度与工程位面

- KMP：**O(n + m)**——主串指针永不回退，next 表 O(m) 预处理
- 对比：朴素 O(n·m)；Boyer-Moore / Horspool（从右往左比，坏字符启发）实际更快；**Sunday 算法**看下一个字符
- 工程：文本编辑器搜索、`grep` 用 BM/Boyer-Moore-Horspool；DNS/路由表的**前缀匹配**是另一族（[[00-信息的表示与处理|信息表示]] 里"前缀自解释"思想的亲戚）
- 王道重 KMP 手算，工程重 BM——面试都问，408 只考前者

## 七、盲点自测

1. 空串和空格串谁长为 0？（空串）
2. 朴素匹配最坏 O(n·m) 的触发条件？（如 "aaaaab" 匹配 "aaab" 类重复前缀）
3. KMP 为什么主串指针不回退？（用已匹配前缀的"相等前后缀"信息滑动模式串）
4. P="abcab" 的 next（王道 1-based）？（0 1 1 1 2）
5. next 和 nextval 的关系？（nextval 跳得更远：若 P[next[j]]==P[j] 则继承 nextval[next[j]]）
6. next[1] 为什么是 0？（模式串头失配，只能主串前进）
7. KMP 总复杂度？（O(n+m)，主串一遍 + 预处理一遍）

## 八、动手玩

```python
# 0-based next 数组（工程写法），对照本文 1-based 手算
def build_next(p):
    nxt = [0] * len(p)          # nxt[0] 恒为 0
    k = 0
    for i in range(1, len(p)):
        while k and p[i] != p[k]:
            k = nxt[k - 1]      # 沿 next 链回退
        if p[i] == p[k]:
            k += 1
        nxt[i] = k
    return nxt

print(build_next("abcab"))      # [0, 0, 0, 1, 2] → 1-based 读作 0,1,1,1,2 ✅

def kmp(s, p):
    nxt = build_next(p)
    k = 0
    for i, c in enumerate(s):   # 主串指针永不回退
        while k and c != p[k]:
            k = nxt[k - 1]
        if c == p[k]:
            k += 1
        if k == len(p):
            return i - k + 1    # 匹配起点
    return -1

print(kmp("abcacc", "abcab"))   # -1
print(kmp("hello abcab world", "abcab"))  # 6
```

## 参考资料

- 王道《数据结构考研复习指导》第 4 章——next 手算的标准口径（1-based）
- 《算法导论》第 32 章——字符串匹配全家福（KMP/Rabin-Karp/后缀树）
- [[00-刷题理模型|刷题理模型]]——字符串题单（滑动窗口、回文，KMP 反而少用）

⬅️ [[03-栈与队列|栈与队列]] 🏠 [[00-基础与理论|00-基础与理论]] ➡️ [[05-树与二叉树|树与二叉树]]