#串与 KMP 模式匹配

#考点定位

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

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

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

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

主串 $$（长 $$）、模式串 $$（长 $$）：逐字符比较，失配则主串指针回退到本轮起点 +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;

最坏情形：$$ aaa...ab，$$ aaab——每轮比到最后一格才失配，比较次数约 $$。

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

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

两个推论：

1. 主串指针 $$ 永不回溯——失配后主串位置 $$ 处的字符接下来与 $$ 比较，所有需要的信息（那段相等的后缀）已经在已匹配前缀里，无需重读主串。这也是 KMP 适合流式读取（管道、网络流）的原因。
2. 预先把每个 $$ 对应的回退位置算成数组，即 next 数组——匹配阶段零回退，整体 $$。

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

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

无满足条件的 $$ 时 $$。直觉表述：$$ = $$ 的最长相等前后缀（border）长度，$$ 就是失配后 $$ 跳到的位置（$$）。

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

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

第 1 步：列出所有 $$ 与对应的前缀 $$，对每个前缀求最长相等前后缀长度：

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

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

#KMP 匹配过程演示（待动画化）

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

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

#nextval：next 的修正及计算

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

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

分步计算表：

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

#KMP 与求 next 的类 C 伪代码

匹配阶段（1 起位序，$$ 长 $$、$$ 长 $$）：

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 的自我匹配"（失配时 $$ 跳自己的 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 起，$$ 约定）为（ ）

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）或逐位多加的典型错误；算完用"接龙自检"复核：$$=a 与 $$=$$=b 不等，$$ 不能由 $$ 得 3 以上的值。

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

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

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

#常见坑

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

#自测

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

答案与简析

1. next = 0 1 1 2 3；nextval：$$：b≠a→1；$$：a=a→nextval[1]=0；$$：b=b→nextval[2]=1；$$：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 回退，比较次数约 $$ 次量级。数字不必背，量级与"i 不回退"机理才是考点。
5. next（1 起）= 0 1 1 1 2（abcac：前缀 abca/abc/ab 均无 border，$$ 前缀 abca border 为 a，长度 1 → next[5]=2）。0 起 + $$ 约定下整体减 1：-1 0 0 0 1。

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