KMP 算法

为什么需要KMP 算法

朴素模式匹配（BF 算法）在匹配失败时，主串指针 i 会回溯到上次开始位置的下一位，模式串指针 j 回到起点，导致大量重复比较。最坏时间复杂度为 O(n×m)。

KMP 算法的核心改进：主串指针 i 永远不回溯。当匹配失败时，利用模式串自身的结构信息（即 next 数组），将模式串向右滑动尽可能远的距离，从而避免无效比较。这是 408 考研中串这一章最重要的算法。

核心思想

KMP 算法的核心特点：

主串不回溯：指针 i 始终向前移动，每次失配只调整模式串指针 j
利用已匹配信息：通过 next 数组记录模式串的"前缀与后缀的最长公共长度"，跳过不可能匹配的位置
预处理模式串：在匹配前先计算 next 数组，匹配过程本身非常高效

BF 与 KMP 的对比：

BF 算法（失配时）：     KMP 算法（失配时）：
主串 i 回溯 ← ←        主串 i 不动
模式串 j 归零           模式串 j = next[j]，向右滑动

交互可视化

通过下方的交互动画，你可以逐步观察KMP 算法的执行过程：

加载可视化中...

操作详解

为什么需要 KMP

以主串 S = "aaaaaab"、模式串 T = "aaab" 为例，BF 算法的匹配过程：

趟数	主串比较位置	比较次数	结果
第1趟	i=1,2,3,4	4次	第4个字符失配，i 回溯到2
第2趟	i=2,3,4,5	4次	第4个字符失配，i 回溯到3
第3趟	i=3,4,5,6	4次	第4个字符失配，i 回溯到4
第4趟	i=4,5,6,7	4次	匹配成功

可以观察到：每次失配后，主串中已经比较过的字符被反复重新比较。KMP 算法正是通过 next 数组避免这些冗余比较——主串指针 i 不回溯，仅调整模式串指针 j。

next 数组求解

next 数组是 KMP 算法的核心。next[j] 的含义是：当模式串第 j 个字符与主串失配时，模式串应回退到第 next[j] 个字符继续比较。

前缀与后缀的最长公共长度

对模式串 T[1..j-1]（即第 j 个字符之前的子串），找其最长相等前后缀的长度 k，则 next[j] = k + 1。

特别规定：next[1] = 0（第1个字符失配，表示主串 i 要后移，模式串从头开始）。

手工求解 next 数组的步骤（⭐ 考研必考）

以模式串 T = "abaabcac" 为例（串下标从 1 开始）：

j	子串 T[1..j-1]	最长相等前后缀	长度 k	next[j] = k+1
1	（空）	—	—	0（规定）
2	`"a"`	无	0	1
3	`"ab"`	无	0	1
4	`"aba"`	`"a"`	1	2
5	`"abaa"`	`"a"`	1	2
6	`"abaab"`	`"ab"`	2	3
7	`"abaabc"`	无	0	1
8	`"abaabca"`	`"a"`	1	2

最终结果：next[] = {0, 1, 1, 2, 2, 3, 1, 2}

求解口诀：看第 j 个字符前面的子串，找它的最长相等前后缀长度，加 1 就是 next[j]。

代码实现（⭐ 考研重点）

cpp

// 求 next 数组（串下标从 1 开始）
void getNext(char T[], int next[], int m) {
    int j = 1, k = 0;
    next[1] = 0;
    while (j < m) {
        if (k == 0 || T[j] == T[k]) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];  // k 回退
        }
    }
}

代码要点：

k == 0 表示已退无可退，next[j+1] = 1
T[j] == T[k] 表示前后缀可以扩展一位，next[j+1] = k+1
k = next[k] 是利用已有 next 值进行回退，这一步的思想和 KMP 匹配过程完全一致

KMP 匹配过程

匹配过程与 BF 类似，但失配时不回溯主串指针 i，而是将模式串指针 j 调整为 next[j]。

cpp

// KMP 匹配算法（串下标从 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]) {
            i++;
            j++;
        } else {
            j = next[j];  // 主串 i 不回溯，模式串 j 回退
        }
    }
    if (j > m)
        return i - m;  // 匹配成功，返回起始位置
    return -1;          // 匹配失败
}

匹配过程关键点：

j == 0 时说明模式串第1个字符就失配了，此时 i++, j++，即主串后移一位，模式串从头开始
S[i] == T[j] 时两个指针同时后移
失配时 j = next[j]，模式串右滑，相当于跳过了不可能匹配的位置

nextval 优化

next 数组存在一个问题：如果 T[j] == T[next[j]]，那么回退到 next[j] 后必然还是失配（因为和同一个字符比较），造成多余比较。

nextval 数组在 next 的基础上做了优化：

cpp

// 求 nextval 数组
void getNextval(char T[], int nextval[], int m) {
    int j = 1, k = 0;
    nextval[1] = 0;
    while (j < m) {
        if (k == 0 || T[j] == T[k]) {
            j++;
            k++;
            if (T[j] != T[k])
                nextval[j] = k;       // 不等时，正常赋值
            else
                nextval[j] = nextval[k]; // 相等时，继续回退
        } else {
            k = nextval[k];
        }
    }
}

手工求 nextval 的方法（⭐ 考研常考）

先求出 next 数组，再逐个修正：对每个 j，若 T[j] == T[next[j]]，则 nextval[j] = nextval[next[j]]；否则 nextval[j] = next[j]。

以 T = "abaabcac" 为例：

j	T[j]	next[j]	T[next[j]]	是否相等	nextval[j]
1	a	0	—	—	0
2	b	1	a	b≠a	1
3	a	1	a	a=a	0（取 nextval[1]）
4	a	2	b	a≠b	2
5	b	2	b	b=b	1（取 nextval[2]）
6	c	3	a	c≠a	3
7	a	1	a	a=a	0（取 nextval[1]）
8	c	2	b	c≠b	2

最终结果：nextval[] = {0, 1, 0, 2, 1, 3, 0, 2}

复杂度分析

阶段	时间复杂度	说明
求 next 数组	O(m)	m 为模式串长度，指针不回溯
KMP 匹配	O(n)	n 为主串长度，主串指针不回溯
总体	O(n+m)	远优于 BF 的 O(n×m)

空间复杂度：O(m)，需要一个长度为 m 的 next（或 nextval）数组。

考研高频考点

⭐ 手工求 next 数组（选择题/填空题每年必考，务必熟练）
⭐ 手工求 nextval 数组（在 next 基础上修正，常与 next 一起考）
⭐ KMP 算法的时间复杂度 O(n+m) 及其与 BF 算法 O(n×m) 的对比
⭐ next 数组的含义：最长相等前后缀长度 +1（概念题）
⭐ KMP 主串指针不回溯的特性（简答题/判断题）
给定 next 数组模拟 KMP 匹配过程（手动模拟题）
next 数组求解代码中 k = next[k] 的含义（代码分析题）

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...

KMP 算法 ​

为什么需要KMP 算法 ​

核心思想 ​

交互可视化 ​

操作详解 ​

为什么需要 KMP ​

next 数组求解 ​

KMP 匹配过程 ​

nextval 优化 ​

复杂度分析 ​

考研高频考点 ​

相关文章