【408数据结构 12】KMP算法：next数组手算+代码，408年年考

专栏导航：本篇是《408数据结构：C++手写实现 + 图解 + 真题》第 12 篇。
上一篇：[【408数据结构 11】稀疏矩阵：三元组与十字链表，转置算法一次讲清]
下一篇：[【408数据结构 13】树与二叉树概念、性质]

文章目录

• 【408数据结构 12】KMP算法：next数组手算+代码，408年年考
• • @[toc]
  • 先做个自测
  • 一、408 怎么考 KMP？先看真题分布
  • 二、字符串的基本概念
  • • 2.1 串的定义
    • 2.2 子串与主串
    • 2.3 模式匹配
  • 三、BF 算法：暴力匹配
  • • 3.1 思路
    • 3.2 图解
    • 3.3 代码实现
    • 3.4 复杂度分析
  • 四、KMP 算法：让主串指针不回退
  • • 4.1 核心思想
    • 4.2 next 数组的含义
    • 4.3 手算 next 数组（下标从 0 开始）
    • 4.4 手算 next 数组（下标从 1 开始）
    • 4.5 图解 KMP 匹配过程
    • 4.6 KMP 代码实现
    • 4.7 复杂度分析
  • 五、nextval 数组：next 的优化
  • • 5.1 为什么需要 nextval
    • 5.2 nextval 的求法
    • 5.3 手算 nextval
    • 5.4 408 常考
  • 六、完整测试代码
  • 七、真题演练
  • • 7.1 next 数组手算
    • 7.2 next 数组含义
    • 7.3 KMP 复杂度
    • 7.4 BF 与 KMP 对比
    • 7.5 nextval 数组
  • 八、一句话记住 KMP
  • 九、总结与下一篇预告

先做个自测

下面这道题，你能 30 秒内算出来吗？

模式串 P = "ababaa"，其 next 数组的值是（ ）。
A. 0 1 1 2 3 4
B. -1 0 0 1 2 3
C. 0 0 1 2 3 1
D. -1 0 0 1 2 1

如果你犹豫了，或者每次求 next 都要从头推，那这篇就是为你写的。

KMP 是 408 字符串章节的必考考点，几乎年年出选择题。
它不难，但 next 数组的下标从 0 还是 1 开始、next 和 nextval 的区别，坑了无数人。

今天我们把 KMP 一次讲透。

---

一、408 怎么考 KMP？先看真题分布

考法	出现频率	典型问法
next 数组手算	★★★★★	给模式串，求 next 数组
nextval 数组手算	★★★★	给模式串，求 nextval 数组
KMP 匹配过程	★★★★	给主串和模式串，问比较次数
BF 与 KMP 对比	★★★★	两者时间复杂度对比
next 数组含义	★★★	next[j] 表示什么
KMP 时间复杂度	★★★★★	求 next 和匹配的复杂度

重点：next 数组手算、KMP 匹配过程，这两个必须拿满分。

---

二、字符串的基本概念

2.1 串的定义

串（String）是由零个或多个字符组成的有限序列，记作：

S = "a1 a2 a3 ... an"

• n 是串的长度。
• n = 0 时称为空串。
• 空格串是由空格组成的串，长度不为 0。

2.2 子串与主串

• 子串：串中任意个连续字符组成的子序列。
• 主串：包含子串的串。
• 模式串：要查找的子串。

例如：

主串：  "ababcabcacbab"
模式串："abcac"

2.3 模式匹配

模式匹配就是在主串中查找模式串第一次出现的位置。

408 常考：

模式匹配的最坏时间复杂度是多少？
答：BF 是 O(n * m)，KMP 是 O(n + m)。

---

三、BF 算法：暴力匹配

3.1 思路

从主串的每个位置开始，逐个与模式串比较。
如果某个字符不匹配，主串指针回退到起始位置的下一个，模式串指针回到开头。

3.2 图解

主串：  a b a b c a b c a c b a b
模式串：a b c a c

第1趟：
主串：  a b a b c a b c a c b a b
模式串：a b c
              ^ 不匹配

第2趟：
主串：  a b a b c a b c a c b a b
模式串：  a b c a c
              ^ 不匹配

第3趟：
主串：  a b a b c a b c a c b a b
模式串：    a b c a c
                  ^ 不匹配

第4趟：
主串：  a b a b c a b c a c b a b
模式串：      a b c a c
                        ^ 不匹配

第5趟：
主串：  a b a b c a b c a c b a b
模式串：        a b c a c
                    匹配成功，位置 5

3.3 代码实现

int BF(const string &s, const string &p) {
    int n = s.length();
    int m = p.length();
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (s[i] == p[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;  // 主串回退
            j = 0;          // 模式串回到开头
        }
    }
    if (j >= m) {
        return i - m;  // 匹配成功，返回起始位置
    }
    return -1;
}

3.4 复杂度分析

• 最好：O(m)，第一次就匹配成功。
• 最坏：O(n * m)，每次都在最后一个字符失配。
• 平均：O(n + m)。

缺点： 主串指针频繁回退，效率低。

---

四、KMP 算法：让主串指针不回退

4.1 核心思想

BF 的问题是：每次失配后，主串指针都要回退。
KMP 的想法是：主串指针不回退，只移动模式串指针。

怎么知道模式串该移动多少？靠 next 数组。

4.2 next 数组的含义

next[j] 表示：当模式串第 j 个字符失配时，模式串应该跳到哪个位置继续比较。

更准确地说：

next[j] = 模式串 P[0..j-1] 的最长相等前后缀的长度。

前缀：不包含最后一个字符的所有子串。
后缀：不包含第一个字符的所有子串。

例如 P = "abab"：

前缀：a, ab, aba
后缀：b, ab, bab
最长相等前后缀：ab，长度 2

4.3 手算 next 数组（下标从 0 开始）

规则：

next[0] = -1
next[1] = 0
next[j] = P[0..j-1] 的最长相等前后缀长度

例：P = "ababaa"

j=0: next[0] = -1
j=1: next[1] = 0
j=2: P[0..1] = "ab"，最长相等前后缀长度 0 -> next[2] = 0
j=3: P[0..2] = "aba"，最长相等前后缀 "a"，长度 1 -> next[3] = 1
j=4: P[0..3] = "abab"，最长相等前后缀 "ab"，长度 2 -> next[4] = 2
j=5: P[0..4] = "ababa"，最长相等前后缀 "aba"，长度 3 -> next[5] = 3

所以：

next = [-1, 0, 0, 1, 2, 3]

答案：B（注意选项 B 是 -1 0 0 1 2 3）

4.4 手算 next 数组（下标从 1 开始）

408 教材（严蔚敏版）使用下标从 1 开始：

next[1] = 0
next[j] = P[1..j-1] 的最长相等前后缀长度 + 1

例：P = "ababaa"（下标从 1 开始）

j=1: next[1] = 0
j=2: P[1..1] = "a"，最长相等前后缀长度 0 -> next[2] = 0 + 1 = 1
j=3: P[1..2] = "ab"，长度 0 -> next[3] = 1
j=4: P[1..3] = "aba"，最长 "a"，长度 1 -> next[4] = 2
j=5: P[1..4] = "abab"，最长 "ab"，长度 2 -> next[5] = 3
j=6: P[1..5] = "ababa"，最长 "aba"，长度 3 -> next[6] = 4

所以：

next = [0, 1, 1, 2, 3, 4]

注意： 两种约定的 next 数组值不同，考试时一定看清题目用的是哪种。

408 常考：

严蔚敏教材中，next[1] = 0，next[j] 是前 j-1 个字符的最长相等前后缀长度 + 1。
下标从 0 开始时，next[0] = -1，next[j] 是前 j 个字符的最长相等前后缀长度。

4.5 图解 KMP 匹配过程

主串：  a b a b c a b c a c b a b
模式串：a b c a c

next（下标从 1 开始）= [0, 1, 1, 2, 3]

第1趟：
主串：  a b a b c a b c a c b a b
模式串：a b c
              ^ 第3个字符失配
next[3] = 1，模式串跳到位置 1

第2趟：
主串：  a b a b c a b c a c b a b
模式串：  a b c a c
              ^ 第3个字符失配
next[3] = 1，模式串跳到位置 1

第3趟：
主串：  a b a b c a b c a c b a b
模式串：    a b c a c
                  ^ 第5个字符失配
next[5] = 3，模式串跳到位置 3

第4趟：
主串：  a b a b c a b c a c b a b
模式串：      a b c a c
                        ^ 第5个字符失配
next[5] = 3，模式串跳到位置 3

第5趟：
主串：  a b a b c a b c a c b a b
模式串：        a b c a c
                    匹配成功，位置 5

注意：主串指针始终没有回退。

4.6 KMP 代码实现

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 求 next 数组（下标从 0 开始）
void GetNext(const string &p, vector<int> &next) {
    int m = p.length();
    next.resize(m);
    next[0] = -1;
    if (m == 1) return;
    next[1] = 0;
    int i = 2, j = 0;
    while (i < m) {
        if (j == -1 || p[i - 1] == p[j]) {
            next[i] = j + 1;
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
}

// KMP 匹配
int KMP(const string &s, const string &p) {
    int n = s.length();
    int m = p.length();
    if (m == 0) return 0;
    vector<int> next;
    GetNext(p, next);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || s[i] == p[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j >= m) {
        return i - m;
    }
    return -1;
}

int main() {
    string s = "ababcabcacbab";
    string p = "abcac";
    cout << KMP(s, p) << endl;  // 5
    return 0;
}

4.7 复杂度分析

• 求 next 数组：O(m)。
• KMP 匹配：O(n)。
• 总时间复杂度：O(n + m)。
• 空间复杂度：O(m)，next 数组。

对比 BF：

算法	时间复杂度	主串指针
BF	O(n * m)	会回退
KMP	O(n + m)	不回退

---

五、nextval 数组：next 的优化

5.1 为什么需要 nextval

如果 P[j] == P[next[j]]，那么跳到 next[j] 后仍然会失配，这次跳转没有意义。
nextval 就是解决这个问题的。

5.2 nextval 的求法

nextval[0] = -1
若 P[j] == P[next[j]]，则 nextval[j] = nextval[next[j]]
否则 nextval[j] = next[j]

5.3 手算 nextval

例：P = "ababaa"（下标从 0 开始）

先求 next：

next = [-1, 0, 0, 1, 2, 3]

再求 nextval：

j=0: nextval[0] = -1
j=1: P[1]='b', P[next[1]]=P[0]='a'，不相等 -> nextval[1] = next[1] = 0
j=2: P[2]='a', P[next[2]]=P[0]='a'，相等 -> nextval[2] = nextval[0] = -1
j=3: P[3]='b', P[next[3]]=P[1]='b'，相等 -> nextval[3] = nextval[1] = 0
j=4: P[4]='a', P[next[4]]=P[2]='a'，相等 -> nextval[4] = nextval[2] = -1
j=5: P[5]='a', P[next[5]]=P[3]='b'，不相等 -> nextval[5] = next[5] = 3

所以：

nextval = [-1, 0, -1, 0, -1, 3]

5.4 408 常考

nextval 数组的作用是什么？
答：优化 next 数组，避免无效跳转，提高匹配效率。

nextval 和 next 的关系？
答：nextval 是 next 的优化版本，当 P[j] == P[next[j]] 时，nextval[j] = nextval[next[j]]。

---

六、完整测试代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 求 next 数组（下标从 0 开始）
vector<int> GetNext(const string &p) {
    int m = p.length();
    vector<int> next(m, 0);
    next[0] = -1;
    if (m == 1) return next;
    next[1] = 0;
    int i = 2, j = 0;
    while (i < m) {
        if (j == -1 || p[i - 1] == p[j]) {
            next[i] = j + 1;
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    return next;
}

// 求 nextval 数组
vector<int> GetNextval(const string &p) {
    vector<int> next = GetNext(p);
    int m = p.length();
    vector<int> nextval(m, 0);
    nextval[0] = -1;
    for (int j = 1; j < m; j++) {
        if (p[j] == p[next[j]]) {
            nextval[j] = nextval[next[j]];
        } else {
            nextval[j] = next[j];
        }
    }
    return nextval;
}

// KMP 匹配
int KMP(const string &s, const string &p) {
    int n = s.length();
    int m = p.length();
    if (m == 0) return 0;
    vector<int> next = GetNext(p);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || s[i] == p[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j >= m) return i - m;
    return -1;
}

int main() {
    string p = "ababaa";
    vector<int> next = GetNext(p);
    vector<int> nextval = GetNextval(p);

    cout << "next:    ";
    for (int x : next) cout << x << " ";
    cout << endl;

    cout << "nextval: ";
    for (int x : nextval) cout << x << " ";
    cout << endl;

    string s = "ababcabcacbab";
    string pat = "abcac";
    cout << "KMP: " << KMP(s, pat) << endl;  // 5

    return 0;
}

运行结果：

next:    -1 0 0 1 2 3 
nextval: -1 0 -1 0 -1 3 
KMP: 5

---

七、真题演练

7.1 next 数组手算

题目：
模式串 P = "ababaa"，其 next 数组（下标从 0 开始）是（ ）。

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

答案：B

7.2 next 数组含义

题目：
KMP 算法中，next[j] 表示（ ）。

A. 模式串第 j 个字符的下标
B. 模式串前 j 个字符的最长相等前后缀长度
C. 主串第 j 个字符的下标
D. 模式串的长度

答案：B

7.3 KMP 复杂度

题目：
KMP 算法的时间复杂度是（ ）。

A. O(n)
B. O(m)
C. O(n + m)
D. O(n * m)

答案：C

7.4 BF 与 KMP 对比

题目：
与 BF 算法相比，KMP 算法的主要优点是（ ）。

A. 空间复杂度更低
B. 主串指针不回退
C. 代码更简单
D. 不需要预处理

答案：B

7.5 nextval 数组

题目：
模式串 P = "aaaab"，其 nextval 数组（下标从 0 开始）是（ ）。

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

答案：B

解析：next = [-1, 0, 1, 2, 3]，nextval = [-1, -1, -1, -1, 0]。

---

八、一句话记住 KMP

next[j] 是前 j 个字符的最长相等前后缀长度。
下标从 0 开始：next[0] = -1。
下标从 1 开始：next[1] = 0。
nextval 优化：相等就继承，不等就用 next。
KMP 主串不回退，时间 O(n+m)。

---

九、总结与下一篇预告

本篇讲了：

• 字符串的基本概念与模式匹配。
• BF 算法的思路、代码与复杂度。
• KMP 算法的核心思想与 next 数组含义。
• next 数组的两种手算方法（下标从 0 和 1 开始）。
• KMP 匹配过程图解。
• nextval 数组的求法与优化。
• 408 真题与易错点。

一句话总结：

KMP 的核心是 next 数组，next 数组的核心是“最长相等前后缀”。把这两个搞懂，KMP 就不再神秘。

下一篇进入树：

【408数据结构 13】树与二叉树概念、性质

我会讲树的定义、二叉树的性质、完全二叉树、满二叉树、二叉树的存储结构，配 408 真题和完整 C++ 代码。

---

专栏导航

• 上一篇：[【408数据结构 11】稀疏矩阵：三元组与十字链表，转置算法一次讲清]
• 下一篇：[【408数据结构 13】树与二叉树概念、性质]
• 专栏目录：[《408数据结构：C++手写实现 + 图解 + 真题》]

标签：数据结构、C++、考研408、计算机考研、算法
分类：数据结构与算法

如果这篇对你有帮助，欢迎点赞、收藏、评论。你的支持是我持续更新的动力。