KMP 模式匹配：从朴素回退到 next 数组

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。串的模式匹配是 408 大纲的核心考点，KMP 的 next 数组几乎年年在选择题里出现，但需要写代码的算法大题一次都没考过它。这是练「暴力→最优」这套方法的绝佳材料。它是经典训练题，不是真题，也不押题。

题目

给定主串 S（长度 n）和模式串 P（长度 m），设计算法找出 P 在 S 中第一次出现的位置（下标从 0 起），不存在则返回 −1。要求分析时间复杂度。

模式匹配是「串」这一章的看家内容。下面按拓展训练的惯例，先写对最朴素的解法，再一步步逼近 KMP。

第一步：把暴力解写对——朴素匹配（BF）

最直接的想法：拿模式串 P 去和主串 S 的每一个可能起点对齐，逐字符比对。从 S 的第 0 位开始贴 P，一位一位比，全对就找到了；中途有一位对不上，就把 P 右移一格、从下一个起点重新贴。

int indexOfBF(char S[], int n, char P[], int m) {
    for (int i = 0; i <= n - m; i++) {   // 枚举每个可能的起点 i
        int j = 0;
        while (j < m && S[i + j] == P[j]) j++;   // 从起点 i 逐字符比对
        if (j == m) return i;            // 整个 P 都匹配上了
    }
    return -1;
}

拿 S = ababcabcacbab、P = abcac 走一遍：从 i=0 贴，ab 对上、第三位 a vs c 失配；i=1 起 b vs a 立刻失配；……一直试到 i=5，abcac 整段对上，返回 5。

复杂度：外层 n 个起点，内层每个起点最坏比 m 次，时间 $O (m n)$ ；只用了 i、j 两个下标，空间 $O (1)$ 。

它值多少分

拓展题按真题同样的两维度看（详见真题专题总纲）：

正确性：BF 枚举了所有起点、逐字符比对，一定能找到第一次出现的位置，结果正确、复杂度分析 $O (m n)$ 与实现一致。正确性维度的分拿得到。
最优性：如果题面要求「尽可能高效」，期望是线性的 $O (m + n)$ 。BF 的 $O (m n)$ 达不到，这一档拿不到。

也就是说，一份写对的 BF 暴力解拿正确性分、丢最优性分。串匹配这道题的最优解 KMP 恰恰是「消除浪费」的教科书案例，值得把它彻底吃透。

暴力解的浪费在哪

用总纲的「找浪费三问」审 BF：

有没有重复扫描？——有，而且藏得很深。关键在失配之后那一步：BF 把 P 右移一格、然后 j 归零从头比，这背后是主串指针 i 也退回去了（下一轮从 i+1 重新开始，而这一轮 i 已经往后读了好几位）。主串里那些刚刚已经比对过、已经确认过内容的字符，被 BF 忘得一干二净，下一轮又要重新读一遍。

举个具体的：P = abcac 在某个起点匹配到 abca 才在第 5 位失配。此时 BF 让主串退回起点的下一位重来。可是——匹配失败的这一刻，我们其实已经知道主串刚读过的那 4 个字符就是 abca。P 自己的结构（前缀 a 和已匹配部分的后缀 a 相同）本可以告诉我们「下一次对齐直接从哪里接着比」，根本不用让主串指针回退。

浪费的本质：主串指针在失配后回退，把已经确认过的字符又读了一遍；而模式串自身的重复结构，本可以让主串指针「只进不退」。

智慧化改造：next 数组让主串指针只进不退

对策是总纲里的第三类手段——利用已知的结构性质。这里的性质是模式串 P 自己的「前缀=后缀」结构：预处理出一个 next 数组，next[j] 表示「P 的前 j 个字符里，最长的『既是前缀又是后缀』的长度」。有了它，一旦在 P 的第 j 位失配，不必让 j 归零、更不必让主串 i 回退，只要把 j 跳到 next[j-1] 继续比——因为那一段前缀已经和刚匹配过的后缀相同，天然对齐，省去重比。

// 构造 next 数组：next[i] = P[0..i] 的最长相等前后缀长度
void buildNext(char P[], int m, int next[]) {
    next[0] = 0;
    int k = 0;                          // k = 当前最长相等前后缀长度
    for (int i = 1; i < m; i++) {
        while (k > 0 && P[i] != P[k]) k = next[k - 1];   // 失配则回退 k
        if (P[i] == P[k]) k++;
        next[i] = k;
    }
}

int indexOfKMP(char S[], int n, char P[], int m) {
    if (m == 0) return 0;
    int *next = (int *)malloc(m * sizeof(int));
    buildNext(P, m, next);

    int j = 0;                          // 模式串已匹配的长度
    for (int i = 0; i < n; i++) {       // 主串指针 i 只进不退
        while (j > 0 && S[i] != P[j]) j = next[j - 1];   // 失配：j 跳回，i 不动
        if (S[i] == P[j]) j++;
        if (j == m) { free(next); return i - m + 1; }    // 完整匹配
    }
    free(next);
    return -1;
}

从暴力解升级过来，几处最容易翻车：

主串指针 i 全程不回退是 KMP 的灵魂。BF 的浪费就是 i 会退，KMP 把「退」的责任全转移给模式串指针 j（跳到 next[j-1]），i 一路向前。写代码时若在失配分支里动了 i，就退化回了 BF。
next 数组的构造本身就是一次 KMP——用 P 匹配 P 自己。buildNext 里的 while (k > 0 && P[i] != P[k]) k = next[k-1] 和主匹配的失配回退是同一个动作，理解了一个就理解了另一个。
next 的定义要和代码里的用法对齐。这里 next[j] 存「前 j+1 个字符的最长相等前后缀长度」，失配时 j 跳到 next[j-1]。不同教材有「next 整体右移一位」「初值填 −1」等变体，定义和使用必须自洽，混用会差一位。
P = abcac 的 next 数组是 [0,0,0,1,0]：只有前缀 abca 的最后一位对应 next=1（前缀 a = 后缀 a）。手算一遍 next 是掌握 KMP 的必经之路。

复杂度：构造 next 是 $O (m)$ ，主匹配中 i 走 n 步、j 的总回退次数不超过它增加的次数，摊还 $O (n)$ ，合计 $O (m + n)$ ；next 数组占 $O (m)$ 空间。这就是把 BF 的重复扫描彻底消除后的结果。

两版对照跑一遍

同一组输入 S = ababcabcacbab、P = abcac（P 出现在下标 5）。先看朴素匹配——注意失配后主串指针回退、大量字符被重复比对：

加载可视化中...

再看 KMP——主串指针 i 一路向前不回退，失配时靠 next 数组让模式串指针跳位：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

等价方法与升级空间

nextval 优化：标准 next 在某些情况下还会做一次「注定失配」的比较（当 P[j] == P[next[j]] 时）。教材里的 nextval 数组在这种情形下再跳一层，减少无效比较。它是 next 的常数级优化，不改变 $O (m + n)$ 的量级，408 选择题里常拿 next 与 nextval 的区别做文章，值得单独手算掌握。
为什么不必用更复杂的算法：Sunday、BM 等算法在工程上平均更快，但它们不在 408 大纲内，考研范围里 KMP 就是模式匹配的最优解，写到 $O (m + n)$ 即到位。

下一步

看 KMP 与 next 数组的交互演示：KMP 可视化
回到方法论源头：「暴力解到最优解」真题专题总纲
同属「串」章节的基础：朴素匹配 BF 的独立讲解见 ds-blog 串章节

KMP 模式匹配：从朴素回退到 next 数组 ​

题目 ​

第一步：把暴力解写对——朴素匹配（BF） ​

它值多少分 ​

暴力解的浪费在哪 ​

智慧化改造：next 数组让主串指针只进不退 ​

两版对照跑一遍 ​

等价方法与升级空间 ​

下一步 ​