04 串与KMP

📚 本文是数据结构的第 4 篇，相关系列见基础与理论。

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

一、串的基本盘

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

⚠️ C 语言的 strlen 是 O(n)（数到 \0）；Java/Python 的 length 是 O(1)（对象头记着）——字符编码里"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/路由表的前缀匹配是另一族（信息表示里"前缀自解释"思想的亲戚）
王道重 KMP 手算，工程重 BM——面试都问，408 只考前者

七、盲点自测

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

八、动手玩

# 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/后缀树）
刷题理模型——字符串题单（滑动窗口、回文，KMP 反而少用）

⬅️ 栈与队列 🏠 00-基础与理论 ➡️ 树与二叉树

04-串与KMP