KMP 算法笔记

KMP 算法是一种改进的字符串匹配算法，由 D.E. Knuth、J.H. Morris 和 V.R. Pratt 提出，因此称为克努特—莫里斯—普拉特算法（简称 KMP 算法）。
KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现通过一个 next() 函数实现，该函数包含模式串的局部匹配信息。
KMP 算法的时间复杂度为 $O(m + n)$。

KMP 原理

例如：有父串 s 和子串 p，要判断子串 p 是否在父串 s 中出现过，或出现多少次。

• 暴力做法：
• 第 1 次：从 s[1] 开始匹配，匹配到第 8 个字符发现 s[8] != p[8]，失败。
• 第 2 次：从 s[2] 开始匹配，但已知 s[2] = 'B' 而 p[1] = 'A'，显然失败。
• 第 3 次：从 s[3] 开始尝试……

• 若 s 长度为 n，p 长度为 m，则暴力解法时间复杂度为 $O(n \times m)$。

• 优化思路：

• 能否跳过中间肯定失败的匹配？
• 答案是肯定的：第 1 次匹配失败时（s[8] != p[8]），观察 p 的前 7 个字符，发现其有长度为 3 的相同前缀和后缀，可直接跳过中间 3 次无效匹配。

s字符串[i-j+ 1,j]这j个字符，和p字符串[1j]字符是一样的。 j往回跳的位置 = p子串[1, j]后缀和前缀相等的最大长度

前缀和后缀相等的最大长度:

ABCDA:1 ABCDABCD: ABABA: 3

next 数组的计算方法

(1) 加快匹配的原理

• 使用 i 遍历主串 s，j 遍历模式串 p。
• 希望：s[i-j+1 ... i] 与 p[1 ... j] 完全一致。
• 当 s[i+1] != p[j+1] 时，需减小 j，且为了效率，新 j 应尽可能大。

• 由于 p[1..3] == p[5..7]，新的 j 最大可设为 3。
• 此时重新检验 s[i+1] 与 p[j+1] 的关系。

关键结论：当 s[i+1] != p[j+1] 时，j 可回跳的最大值 = p[1..j] 中最大相同前缀与后缀的长度。

(2) next 数组的含义

• 定义：next[j] 表示模式串 p 中前 j 个字符的最大相同前缀和后缀的长度。
• 注意：不包含整个字符串本身。
  例如：字符串 "ABABA" 的最大相同前后缀长度是 3（"ABA"），而不是 5。
• 特别地：next[0] = next[1] = 0。

(3) 高效匹配过程

• 当 s[i+1] != p[j+1] 时，令 j = next[j] 回跳；
• 若 s[i+1] == p[j+1]，则继续向后匹配。
• （注：为避免与系统函数名冲突，next 数组常缩写为 ne）

(4) 高效求 next 数组

• 求 next 数组的过程本质上是模式串 p 自己与自己进行匹配。
• 方法类似于 KMP 匹配过程。

代码模板

建议下标从1开始，比较好写

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}

KMP 算法时间复杂度分析：为什么是 O(n + m)？

KMP 算法的总时间复杂度为 O(n + m)，其中： - n 是主串（文本串）长度， - m 是模式串（子串）长度。

该复杂度由两部分组成： 1. 构建 next 数组：O(m) 2. 主串与模式串匹配过程：O(n)

下面分别详细说明。

一、匹配过程的时间复杂度：O(n)

在 KMP 的主匹配循环中：

• 主串指针 i 从左到右单调递增，最多执行 n 次（不回退）。
• 模式串指针 j 在匹配成功时 j++，失配时通过 j = next[j] 回退。

关键观察：

• 每次 j++ 都对应一次 i++，因此 j 的总前进次数 ≤ n。
• j 的值始终满足 0 ≤ j ≤ m，且每次回退都会使 j 减小。
• j 的总回退次数不可能超过其总前进次数（因为不能减到负数）。

因此，整个匹配过程中，j 的变化（前进 + 回退）总次数 ≤ 2n，故匹配阶段时间复杂度为 O(n)。

二、构建 next 数组的时间复杂度：O(m)

构建 next 数组的过程本质上是模式串自己与自己进行 KMP 匹配：

• 使用两个指针（如 i 和 j）遍历模式串 p[0..m-1]。
• i 从 1 到 m−1 单调递增；
• j 在失配时回退（j = next[j]），但同样受前进次数限制。

同理：

• j 的总前进次数 ≤ m；
• 总回退次数 ≤ 总前进次数；
• 整个预处理过程的操作次数 ≤ 2m。

因此，构建 next 数组的时间复杂度为 O(m)。

三、为何不是 O(n·m)？

暴力匹配的复杂度为 O(n·m)，是因为： - 每次失配后，主串指针可能“逻辑上”回退（重新从下一个起始位置开始匹配）； - 导致大量重复比较。

而 KMP 的优势在于： - 主串指针 i 永远不回退，只遍历一次； - 模式串指针 j 的回退是“智能跳转”，利用已匹配信息避免无效比较； - 虽然 j 可能多次回退，但所有回退的总代价被严格限制在线性范围内。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com