#串与 KMP 模式匹配

#考点定位

• 所属大纲章节：串的定义与实现、串的模式匹配（朴素模式匹配、KMP 算法）
• 常见题型：选择题（next / nextval 数组手算、匹配过程某一步的指针位置、复杂度）；大题极少独立命题
• 考查频率：高（选择题）。next 数组手算是 408 数据结构选择题的经典保留项目

工程直觉迁移：日常 str.find / strstr 底层即此类算法。但工程里从不手算 next，手算速度与准确率就是本节唯一目标。

#串的严格定义与相关术语

• 串：由零个或多个字符组成的有限序列，记为 $S = 'a_1 a_2 \ldots a_n'\ (n \ge 0)$。字符个数 $n$ 称为串的长度；串本质上是元素限定为字符的线性表（线性表的定义见 02-线性表）。
• 空串：长度为 0 的串（不含任何字符）；空格串：由一个或多个空格字符组成的串（长度 $\ge 1$）。经典对比：空串长度为 0，空格串长度等于其空格个数；空串是任何串的子串。选择题最爱把二者混为一谈。
• 子串：串中任意个连续字符组成的子序列（空串与串本身也是子串）；主串：包含子串的原串。子串的位置以其首字符在主串中的位序表示。
• 模式匹配：在主串中查找与模式串相等的子串的过程，结果为匹配的起始位置或"匹配失败"。下文的 BF 与 KMP 都是模式匹配算法。

#从暴力匹配到 KMP：动机推导

#暴力匹配（BF）及其最坏情形

主串 $S$（长 $n$）、模式串 $T$（长 $m$）：逐字符比较，失配则主串指针回退到本轮起点 +1，模式串回到开头。

int i = 1, j = 1;
while (i <= n && j <= m) {
    if (S[i] == T[j]) { i++; j++; }
    else { i = i - j + 2;  j = 1; }   // 主串回退到本轮起点的下一位
}
if (j > m) return i - m;   // 匹配成功，返回起始位序
else return 0;

最坏情形：$S =$ aaa...ab，$T =$ aaab——每轮比到最后一格才失配，比较次数约 $(n - m + 1) \times m = O(nm)$。

#KMP 的核心观察：失配信息蕴含在已匹配前缀里

设失配时 $T$ 的已匹配部分为 $T_1..T_{j-1}$（它与主串对应段完全相等）。此时主串失配位置的字符与谁比较，只由 $T_1..T_{j-1}$ 自身的重复结构决定：若 $T$ 的某前缀 $T_1..T_{k-1}$ 恰好等于 $T_1..T_{j-1}$ 的长度为 $k-1$ 的后缀，则可将 $T$ 右移，让 $T_1..T_{k-1}$ 对齐到刚才那段后缀上，直接从 $T_k$ 与主串失配字符继续比较。

两个推论：

1. 主串指针 $i$ 永不回溯——失配后主串位置 $i$ 处的字符接下来与 $T_k$ 比较，所有需要的信息（那段相等的后缀）已经在已匹配前缀里，无需重读主串。这也是 KMP 适合流式读取（管道、网络流）的原因。
2. 预先把每个 $j$ 对应的回退位置算成数组，即 next 数组——匹配阶段零回退，整体 $O(n + m)$（渐进符号的严格定义见 01-绪论与复杂度分析）。

#next 数组：定义与手算流程

约定（严蔚敏教材，408 主流；位序从 1 起）：$next[1] = 0$，且

$next[j] = \max\{\, k \mid 1 < k < j,\ T_1..T_{k-1} = T_{j-k+1}..T_{j-1} \,\}$

无满足条件的 $k$ 时 $next[j] = 1$。直觉表述：$next[j] - 1$ = $T_1..T_{j-1}$ 的最长相等前后缀（border）长度，$next[j]$ 就是失配后 $j$ 跳到的位置（$next[j] = \text{border} + 1$）。

两秒出结论的特例（选择题提速）：$next[1] = 0$；$next[2] = 1$ 恒成立（单字符无真前后缀）。

#手算流程（模式串 T = ababaa，模拟题）

第 1 步：列出所有 $j$ 与对应的前缀 $T_1..T_{j-1}$，对每个前缀求最长相等前后缀长度：

第 2 步：横排写出结果（这是答题卷面上的最终形态）：

手算心法：不要逐格从定义硬抠，用"接龙法"——$next[j+1]$ 至多是 $next[j]+1$：若 $T[j] = T[next[j]]$，则 $next[j+1] = next[j]+1$；否则像匹配失配一样让 $j$ 连续跳 $next$ 链回退重试（递归定义本身）。全同字符串 aaaa 的 next 是 0 1 2 3（每步都 +1），用它可以快速自检接龙法。

#KMP 匹配过程演示（另配单步交互动画，见交互演示页 KMP 模式匹配）

主串 $S$ = abababaababaa，模式串 $T$ = ababaa（$next$ = 0 1 1 2 3 4）。只演示失配关键步：

注意步骤 2-3：主串指针从 6 到 8 单调前进，回退只发生在模式串指针 $j$ 上。

#nextval：next 的修正及计算

next 的缺陷：失配跳到 $next[j]$ 后，若 $T[next[j]] = T[j]$，则该字符与主串失配位置的比较必然再次失败（同一个字符换个位置再比一次）。

修正规则（1 起，逐位计算，模拟题示例沿用 $T$ = ababaa）：

$nextval[1] = 0;\qquad nextval[j] = \begin{cases} nextval[next[j]] & \text{若 } T[j] = T[next[j]] \\ next[j] & \text{若 } T[j] \ne T[next[j]] \end{cases}$

分步计算表：

结果：$next$ = 0 1 1 2 3 4，$nextval$ = 0 1 0 1 0 4。nextval 在最坏情形下显著减少重复比较（如 $T$ = aaaab：$next$ = 0 1 2 3 4，$nextval$ = 0 0 0 0 4），两者匹配结果的正确性相同。

#KMP 与求 next 的类 C 伪代码

匹配阶段（1 起位序，$S$ 长 $n$、$T$ 长 $m$）：

int KMP(char S[], char T[], int next[], int n, int m) {
    int i = 1, j = 1;
    while (i <= n && j <= m) {
        if (j == 0 || S[i] == T[j]) {   // j==0：T 已滑到头，i、j 同进
            i++;  j++;
        } else {
            j = next[j];                // 主串 i 不动，仅模式串回退
        }
    }
    if (j > m) return i - m;            // 匹配成功，返回起点
    return 0;
}

求 next 本质是"T 与 T 的自我匹配"（失配时 $j$ 跳自己的 next 链），代码结构与上面对称：

void GetNext(char T[], int next[], int m) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < m) {
        if (j == 0 || T[i] == T[j]) {
            i++;  j++;
            next[i] = j;               // 接龙：相等则 border 长 1
        } else {
            j = next[j];               // 回退重试
        }
    }
}

选择题一般不考代码，但理解"接龙法 = 这段代码的手工执行"能把手算从逐格抠定义提速到秒级。

#两套 next 约定对照（防干扰项）

两套值整体相差 1。题面若给出 next 数组首项或明确定义，以题面为准；408 真题曾出现两种约定混入选项的情形，先判断题面约定再代入。

例 1：模式串 abaabc 的 next 数组（1 起，$next[1]=0$ 约定）为（ ）

A. 0 1 1 2 3 3 B. 0 1 1 2 2 3 C. 0 1 1 2 3 2 D. 0 1 2 2 3 1

解答：逐位算 border（最长相等前后缀）：

得 0 1 1 2 2 3，选 B。错因提醒：选项 A/C/D 的第 4-6 位是把 border 长度直接当 next 值（少加 1）或逐位多加的典型错误；算完用"接龙自检"复核：$T_5$=a 与 $T_{next[5]}$=$T_2$=b 不等，$next[6]$ 不能由 $next[5]+1$ 得 3 以上的值。

例 2（改用标准选择题形态）：模式串 abcabca，$next[7]$ 的值为（ ）

A. 3 B. 4 C. 5 D. 6

解答：$next[7]$ 对应前缀 abcabc，最长相等前后缀为 abc（长度 3），$next[7] = 4$，选 B。错因提醒：border 取最长者，短前后缀 a（长度 1 → next=2）也是候选但非最大。

#常见坑

1. 约定先行：408 主流采用"1 起位序 + $next[1]=0$"（严蔚敏）；部分资料用 0 起位序 + $next[0] = -1$（值整体差 1）。答题前先看题面对 next 的定义或给的首项值，选择题选项常把两套约定混入干扰项。
2. $next[j]$ 由 $T_1..T_{j-1}$ 决定，与 $T_j$ 本身无关（nextval 才用到 $T_j$）。选择题会把"求 next[5]"的依据画蛇添足地包含 $T_5$，是陷阱。
3. nextval 的"相等则取 nextval[next[j]]"，不是取 next[next[j]]——修正要沿 nextval 链传递，否则遇到链式相等（aaaa...）会算错。
4. KMP 时间复杂度 $O(n+m)$ 的证明思路（选择题考过结论）：$i$ 单调不减且至多增 $n$ 次，$j$ 的总回退量不超过总增长量（均摊论证），与 BF 的 $O(nm)$ 对照。
5. 求解 next 数组本身可以看作"T 与 T 的自我匹配"（$j$ 跳自己的 next 链），手算时"接龙法"即此原理，不必查表背诵。
6. 高频模式串 next/nextval 速查（考前 5 分钟自检用，1 起、$next[1]=0$ 约定）：

#自测

1. 模式串 ababa 的 next 与 nextval 数组（1 起，$next[1]=0$）。
2. 模式串 aaaab 的 next 与 nextval 数组。
3. 用一句话回答：为什么 KMP 中主串指针可以不回溯？
4. BF 算法在 $S$ = aaaaab（$n=6$）、$T$ = aab 下的比较次数？KMP 下呢？
5. 模式串 abcac 的 next 数组，以及若把 next[1] 约定为 $-1$（0 起位序）时整个数组如何变化？

答案与简析

1. next = 0 1 1 2 3；nextval：$j{=}2$：b≠a→1；$j{=}3$：a=a→nextval[1]=0；$j{=}4$：b=b→nextval[2]=1；$j{=}5$：a=a→nextval[3]=0。nextval = 0 1 0 1 0。
2. next = 0 1 2 3 4；nextval = 0 0 0 0 4（最后一格 b 与 T[next[5]]=a 不等，保 4）。
3. 失配时，主串失配位置左侧的字符段与模式串前缀相等，用前缀自身的 border 结构即可确定下一步对齐位置，无需重读主串已扫过的字符。
4. BF：3 轮 × 各 3 次（近似），准确数：第 1 轮比 3 次成功匹配（aaa vs aab 第 3 次失配，比了 3 次）、第 2 轮 3 次、第 3 轮 3 次、第 4 轮 3 次成功 → 约 12 次。KMP：j 链回退替换 i 回退，比较次数约 $n + m = 9$ 次量级。数字不必背，量级与"i 不回退"机理才是考点。
5. next（1 起）= 0 1 1 1 2（abcac：前缀 abca/abc/ab 均无 border，$j{=}5$ 前缀 abca border 为 a，长度 1 → next[5]=2）。0 起 + $next[0]=-1$ 约定下整体减 1：-1 0 0 0 1。

下一步：本章是纯选择题考点，学完立即做 01-线性表与栈队列-章节测 中相关题目巩固（KMP 专项变式题将随定向测补入）。