KMP 算法详解：只需这一篇文章，从零开始彻底理解KMP算法

LiUEEEEE

94人浏览 · 2026-06-05 18:04:20

LiUEEEEE · 2026-06-05 18:04:20 发布

KMP 算法详解：只需这一篇文章，从零开始彻底理解KMP算法

                        博主主页：LiUEEEEE
                          C++专栏
                         C语言专栏
                        数据结构专栏
                        排序算法专栏
                       力扣牛客经典题目专栏

一、引言：我们要解决什么问题？

假设你有两个字符串：

文本串 S："ABABDABACDABABCABAB"
模式串 P："ABABCABAB"

你想知道：P 是否出现在 S 中？如果出现，在哪个位置？

这个问题叫做 字符串匹配，是计算机科学中最基础的问题之一。

二、暴力解法（BF 算法）

最直觉的思路：从 S 的每一个位置开始，逐个字符与 P 比较。

S: A B A B D A B A C D A B A B C A B A B
P: A B A B C A B A B        ← 比到这里发现不匹配（第5个字符）
         ↑ 失配位置

然后把 P 往右挪一格，重新从头开始比：
S: A B A B D A B A C D A B A B C A B A B
P:   A B A B C A B A B      ← 又要从头比

暴力法的最坏时间复杂度是 O(n × m)，其中 n 是 S 的长度，m 是 P 的长度。当 n 和 m 都很大时，效率很低。

核心问题：暴力法每次失配后，把模式串只向右移动了一位，然后已经比较过的字符全部作废，重新来过。

三、KMP 的核心思想：利用已匹配的信息

KMP 算法（Knuth-Morris-Pratt，三位发明者的名字）的精髓就一句话：

失配时，不要从头再来。利用已经匹配成功的那部分字符信息，让模式串尽可能多地向右滑动。

3.1 一个直觉的例子

S: A B A B D A B A C D ...
P: A B A B C A B A B
        ↑ 第5个字符失配（B ≠ C）

我们已经知道 S 的前 4 个字符是 ABAB，和 P 的前 4 个字符完全一样。

关键观察：P 的前 4 个字符 ABAB 中，前缀 AB 和后缀 AB 是相同的！

这意味着：S 中失配位置之前的 AB（后缀），其实已经和 P 的前两个字符（前缀 AB）匹配过了。我们不需要再比较它们！

所以我们可以把 P 直接滑动，让 P 的第 3 个字符对准 S 的失配位置：

S: A B A B D A B A C D ...
P:     A B A B C A B A B    ← 直接跳到这个位置，省去了中间的比较

这就是 KMP 的全部奥秘：通过预处理模式串，提前知道"失配时可以跳多远"。

四、next 数组（前缀函数）—— KMP 的灵魂

4.1 什么是 next 数组？

对于模式串 P 的每一个位置 i，我们定义 next[i] 为：

P[0..i] 这个子串中，最长的相等的真前缀和真后缀的长度。

几个概念澄清：

前缀：从第一个字符开始、不包含最后一个字符的连续子串。例如 "ABAB" 的前缀有："A", "AB", "ABA"。
后缀：从最后一个字符开始、不包含第一个字符的连续子串。例如 "ABAB" 的后缀有："B", "AB", "BAB"。
真前缀/后缀：就是不等于原串本身的前缀/后缀。

4.2 手动计算 next 数组

以模式串 P = "ABABCABAB" 为例，我们逐个位置计算：

位置 i	子串 P[0…i]	所有相等的前后缀	最长长度	next[i]
0	`"A"`	无（单字符没有真前后缀）	0	0
1	`"AB"`	前缀`"A"` ≠ 后缀`"B"`	0	0
2	`"ABA"`	前缀`"A"` = 后缀`"A"`	1	1
3	`"ABAB"`	前缀`"AB"` = 后缀`"AB"`	2	2
4	`"ABABC"`	前缀`"A"` = 后缀`"C"`? 不等。最长为 0	0	0
5	`"ABABCA"`	前缀`"A"` = 后缀`"A"`	1	1
6	`"ABABCAB"`	前缀`"AB"` = 后缀`"AB"`	2	2
7	`"ABABCABA"`	前缀`"ABA"` = 后缀`"ABA"`	3	3
8	`"ABABCABAB"`	前缀`"ABAB"` = 后缀`"ABAB"`	4	4

所以 next 数组为：

P:     A  B  A  B  C  A  B  A  B
next:  0  0  1  2  0  1  2  3  4

4.3 next 数组的含义

next[i] = k 意味着：

P[0..k-1] = P[i-k+1..i]（长度为 k 的前缀 = 长度为 k 的后缀）
当 P[i+1] 失配时，我们可以把模式串的第 k 个字符（P[k]）对准失配位置继续比较
而不是从 P[0] 重新开始

换句话说：next[i] 告诉我们，当第 i+1 个字符失配时，模式串应该滑动到哪里。

五、next 数组的构建——最难理解的部分

暴力计算 next 数组很简单（对每个位置，枚举所有前后缀长度），但 KMP 的精髓在于用 O(m) 的时间构建它。构建过程本身就是一个"自己对自己做 KMP 匹配"的过程。

5.1 核心递推逻辑

假设我们已经求出了 next[0] 到 next[i-1]，现在要求 next[i]。

设 j = next[i-1]（上一个位置的最长相等前后缀长度）。

我们看 P[j] 是否等于 P[i]：

如果相等：next[i] = j + 1。太好了，前面的前后缀可以扩展一位。
如果不相等：我们需要"回退"——看 P[0..i-1] 中次长的相等前后缀是多少。

回退的关键：次长的相等前后缀长度就是 next[j-1]！

5.2 为什么可以回退？

这是一个精妙的递推关系。用图来理解：

P: ... A B A B C A B A B ...
       ←─j─→         ←─i─→

假设 next[i-1] = j，说明 P[0..j-1] = P[i-j..i-1]。

如果 P[j] ≠ P[i]，我们需要找一个更短的相等前后缀。那就在 P[0..j-1]（即 P[i-j..i-1]）这个子串里找——这正好就是 next[j-1] 能告诉我们的！

这就是"自己对自己做匹配"的含义。

5.3 代码实现

vector<int> buildNext(const string& P) {
    int m = P.size();
    vector<int> next(m, 0);

    // i 从 1 开始，因为 next[0] 恒为 0
    int j = 0; // j 表示当前已匹配的前缀长度
    for (int i = 1; i < m; i++) {
        // 如果 P[j] != P[i]，就不断回退
        while (j > 0 && P[j] != P[i]) {
            j = next[j - 1];
        }
        // 如果 P[j] == P[i]，前缀长度加 1
        if (P[j] == P[i]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

5.4 手动模拟构建过程

以 P = "ABABCABAB" 为例：

i=1: j=0, P[0]='A' ≠ P[1]='B' → j=0, next[1]=0
i=2: j=0, P[0]='A' == P[2]='A' → j=1, next[2]=1
i=3: j=1, P[1]='B' == P[3]='B' → j=2, next[3]=2
i=4: j=2, P[2]='A' ≠ P[4]='C'
     回退：j = next[1] = 0
     j=0, P[0]='A' ≠ P[4]='C' → j=0, next[4]=0
i=5: j=0, P[0]='A' == P[5]='A' → j=1, next[5]=1
i=6: j=1, P[1]='B' == P[6]='B' → j=2, next[6]=2
i=7: j=2, P[2]='A' == P[7]='A' → j=3, next[7]=3
i=8: j=3, P[3]='B' == P[8]='B' → j=4, next[8]=4

结果：next = [0, 0, 1, 2, 0, 1, 2, 3, 4]，和之前手动推导的一致。

六、KMP 匹配过程

有了 next 数组，匹配就变得很简单了。

6.1 核心逻辑

用两个指针 i（指向 S）和 j（指向 P）从左到右扫描：

如果 S[i] == P[j]：两个指针都前进。
如果 S[i] != P[j]（失配）：
- 如果 j > 0：把 j 移动到 next[j-1]（利用已匹配信息滑动），i 不动。
- 如果 j == 0：模式串无法再滑动了，只移动 i。
如果 j == m（整个模式串匹配成功）：记录匹配位置 i - m，然后把 j 移到 next[j-1] 继续找下一个匹配。

6.2 完整匹配示例

S: A B A B D A B A C D A B A B C A B A B
P: A B A B C A B A B
next: 0 0 1 2 0 1 2 3 4

第 1 轮：
i=0,j=0: S[0]='A' == P[0]='A' → i=1,j=1
i=1,j=1: S[1]='B' == P[1]='B' → i=2,j=2
i=2,j=2: S[2]='A' == P[2]='A' → i=3,j=3
i=3,j=3: S[3]='B' == P[3]='B' → i=4,j=4
i=4,j=4: S[4]='D' ≠ P[4]='C' → 失配！
         j = next[3] = 2（滑动！P 的第3个字符对准位置4）
         （相当于 P 向右滑了 2 格）

i=4,j=2: S[4]='D' ≠ P[2]='A' → 失配！
         j = next[1] = 0

i=4,j=0: S[4]='D' ≠ P[0]='A' → 失配！
         j 已经是 0，i++

i=5,j=0: S[5]='A' == P[0]='A' → i=6,j=1
i=6,j=1: S[6]='B' == P[1]='B' → i=7,j=2
i=7,j=2: S[7]='A' == P[2]='A' → i=8,j=3
i=8,j=3: S[8]='C' ≠ P[3]='B' → 失配！
         j = next[2] = 1

i=8,j=1: S[8]='C' ≠ P[1]='B' → 失配！
         j = next[0] = 0

i=8,j=0: S[8]='C' ≠ P[0]='A' → 失配！i++

i=9,j=0: S[9]='D' ≠ P[0]='A' → 失配！i++

i=10,j=0: S[10]='A' == P[0]='A' → i=11,j=1
i=11,j=1: S[11]='B' == P[1]='B' → i=12,j=2
i=12,j=2: S[12]='A' == P[2]='A' → i=13,j=3
i=13,j=3: S[13]='B' == P[3]='B' → i=14,j=4
i=14,j=4: S[14]='C' == P[4]='C' → i=15,j=5
i=15,j=5: S[15]='A' == P[5]='A' → i=16,j=6
i=16,j=6: S[16]='B' == P[6]='B' → i=17,j=7
i=17,j=7: S[17]='A' == P[7]='A' → i=18,j=8
i=18,j=8: S[18]='B' == P[8]='B' → i=19,j=9

j == 9 == m → 匹配成功！位置 = 19 - 9 = 10

匹配结果：模式串在文本串的位置 10 处找到。

6.3 KMP 的巧妙之处

注意第 1 轮失配后，i 始终没有回退！它只向右移动。失配时通过移动 j（模式串指针）来实现"滑动"。这保证了时间复杂度为 O(n)。

七、完整 C++ 代码

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

/**
 * 构建 next 数组（前缀函数）
 * next[i] = P[0..i] 中最长的相等真前缀和真后缀的长度
 */
vector<int> buildNext(const string& P) {
    int m = P.size();
    vector<int> next(m, 0);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && P[j] != P[i]) {
            j = next[j - 1];
        }
        if (P[j] == P[i]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

/**
 * KMP 搜索
 * 返回所有匹配位置（在 S 中的起始下标）
 */
vector<int> kmpSearch(const string& S, const string& P) {
    vector<int> result;
    if (P.empty()) return result;

    vector<int> next = buildNext(P);
    int n = S.size(), m = P.size();
    int j = 0; // 模式串指针

    for (int i = 0; i < n; i++) {
        while (j > 0 && S[i] != P[j]) {
            j = next[j - 1];
        }
        if (S[i] == P[j]) {
            j++;
        }
        if (j == m) {
            result.push_back(i - m + 1); // 记录匹配位置
            j = next[j - 1]; // 继续寻找下一个匹配
        }
    }
    return result;
}

int main() {
    string S = "ABABDABACDABABCABAB";
    string P = "ABABCABAB";

    cout << "文本串: " << S << endl;
    cout << "模式串: " << P << endl;

    // 打印 next 数组
    vector<int> next = buildNext(P);
    cout << "next数组: ";
    for (int val : next) {
        cout << val << " ";
    }
    cout << endl;

    // KMP 搜索
    vector<int> matches = kmpSearch(S, P);
    if (matches.empty()) {
        cout << "未找到匹配" << endl;
    } else {
        cout << "匹配位置: ";
        for (int pos : matches) {
            cout << pos << " ";
        }
        cout << endl;
    }

    return 0;
}

运行结果

文本串: ABABDABACDABABCABAB
模式串: ABABCABAB
next数组: 0 0 1 2 0 1 2 3 4
匹配位置: 10

八、时间复杂度分析

阶段	复杂度
构建 next 数组	O(m)
KMP 匹配	O(n)
总计	O(n + m)

为什么是线性的？关键在于：

i（文本串指针）只会向右移动，从不回退。
j（模式串指针）虽然会回退，但每次回退至少减少 1，而 j 最多增加 n 次（每匹配成功一次 i 增加，j 最多增加到 m）。
所以总的比较次数不超过 2n，即 O(n)。

九、常见疑问

Q1: next 数组下标从 1 开始的写法？

很多教材（尤其是中文教材）把 next 数组下标从 1 开始，并且 next[1] = 0。这时代码的写法会略有不同，但逻辑完全一样。本文采用下标从 0 开始的写法，更符合 C++ 的习惯。

Q2: nextval 数组是什么？

标准的 next 数组有一个小瑕疵：当 P[next[i]] == P[i] 时，回退到 next[i] 仍然会失配（因为这两个字符相同），等于浪费了一次比较。nextval 数组就是对此的优化——如果回退后字符相同，就继续回退。

vector<int> buildNextval(const string& P) {
    int m = P.size();
    vector<int> nextval(m, 0);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && P[j] != P[i]) {
            j = nextval[j - 1];
        }
        if (P[j] == P[i]) {
            j++;
        }
        // 优化：如果回退后的字符和当前位置相同，继续回退
        if (i + 1 < m && P[j] == P[i + 1]) {
            nextval[i] = nextval[j - 1];
        } else {
            nextval[i] = j;
        }
    }
    return nextval;
}