在字符串匹配领域，KMP 算法是当之无愧的 “经典标杆”—— 它解决了传统暴力匹配的低效问题，能在 O (n + m) 时间内完成主串与模式串的匹配（n 为主串长度，m 为模式串长度），避免了暴力匹配中大量的无效回溯。无论是算法面试、竞赛，还是实际开发中的字符串检索场景，KMP 都是必备知识点。本文将从暴力匹配的痛点出发，拆解 KMP 的核心原理、next 数组构建，再到实战例题，带你从零到一掌握 KMP 算法。

一、先搞懂：暴力匹配的痛点的是什么？

在学习 KMP 之前，我们先明确传统暴力匹配的问题，才能理解 KMP 的优化逻辑。

1. 暴力匹配流程

给定主串 s（长度 n）和模式串 p（长度 m），暴力匹配的思路是：

1. 主串指针 i 从 0 开始，模式串指针 j 从 0 开始；
2. 若 s[i] == p[j]，则 i 和 j 同时后移，继续匹配；
3. 若匹配失败（s[i] != p[j]），则 i 回溯到 i - j + 1，j 重置为 0，重新开始匹配；
4. 重复上述步骤，直到 j == m（匹配成功）或 i >= n（匹配失败）。

2. 暴力匹配的低效根源

暴力匹配的时间复杂度是 O (n×m)，最坏情况下（如主串为 "aaaaa..."，模式串为 "aaab"），每次匹配到模式串末尾才失败，导致大量无效回溯。例如：

• 主串：s = "ABCABCDABABCDABCDABDE"
• 模式串：p = "ABCDABD"
• 当匹配到 s[6] = 'C' 与 p[6] = 'D' 失败时，暴力匹配会让 i 回溯到 1，j 重置为 0，重新匹配 —— 但此时主串前几位的前缀已存在可复用的匹配信息，无需完全回溯。

3. 核心矛盾

暴力匹配的问题在于：匹配失败时，主串指针 i 不必要的回溯。KMP 的核心优化思路就是：匹配失败时，主串指针 i 不回溯，仅通过调整模式串指针 j 的位置，利用已匹配部分的前缀信息，直接从合适的位置继续匹配。

二、KMP 核心：next 数组（前缀函数）

KMP 的精髓在于 next 数组（也叫前缀函数），它是模式串的 “自我匹配表”，记录了模式串中每个位置 j 对应的 “最长相等前后缀长度”—— 这正是实现无回溯匹配的关键。

1. 什么是 “最长相等前后缀”？

对于模式串 p 的第 j 个位置（以 0 为起点），其前缀是指从 p[0] 到 p[j-1] 的子串，后缀是指从 p[1] 到 p[j] 的子串（注意：前缀和后缀不能是整个子串）。“最长相等前后缀长度” 就是前缀和后缀中最长且相等的子串长度。

示例（模式串 p = "ABCDABD"）

模式串索引 j	0	1	2	3	4	5	6
模式串字符	A	B	C	D	A	B	D
next[j]	0	0	0	0	1	2	0

• j=4（字符 'A'）：前缀为 "ABCD" 的前缀（"A"），后缀为 "ABCD" 的后缀（"A"），最长相等前后缀长度为 1，故 next[4] = 1；
• j=5（字符 'B'）：前缀为 "ABC DA" 的前缀（"AB"），后缀为 "ABC DA" 的后缀（"AB"），最长相等前后缀长度为 2，故 next[5] = 2；
• 其他位置无相等前后缀，故 next[j] = 0。

2. next 数组的作用

当模式串 p[j] 与主串 s[i] 匹配失败时，无需回溯 i，只需将 j 调整为 next[j]，继续匹配 s[i] 与 p[next[j]]。原因：next[j] 对应的最长相等前后缀，意味着模式串前 next[j] 个字符已与主串当前位置的前 next[j] 个字符匹配，无需重新匹配这部分内容。

三、手把手教你：构建 next 数组（2 种实现方式）

构建 next 数组是 KMP 的核心难点，下面从基础到优化，拆解 3 种实现方式，帮你彻底理解。

1. 基础版 next 数组（易理解）

核心思路：用两个指针 i（后缀末尾）和 j（前缀末尾），遍历模式串，逐步计算每个位置的最长相等前后缀长度。

实现步骤

1. 初始化 next 数组为 0，j = 0（前缀末尾指针）；
2. i 从 1 开始遍历模式串（后缀末尾从 1 开始，避免整个子串为前缀 / 后缀）；
3. 若 p[i] == p[j]：j 后移，next[i] = j，i 后移；
4. 若 p[i] != p[j]：若 j > 0，则 j = next[j-1]（回溯到上一个可能匹配的前缀）；若 j == 0，则 next[i] = 0，i 后移；
5. 重复步骤 3-4，直至遍历完成。

代码实现

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_M = 10005;
char p[MAX_M];
int next_arr[MAX_M];
int m;

void get_next() {
    int j = 0;
    next_arr[0] = 0;
    for (int i = 1; i < m; ++i) {
        while (j > 0 && p[i] != p[j]) {
            j = next_arr[j - 1];
        }
        if (p[i] == p[j]) {
            j++;
        }
        next_arr[i] = j;
    }
}

int main() {
    cin >> p;
    m = strlen(p);
    get_next();
    for (int i = 0; i < m; ++i) {
        cout << next_arr[i] << " ";
    }
    return 0;
}

2. 优化版 next 数组（解决重复回溯）

基础版 next 数组存在一个问题：当 p[j] == p[next[j]] 时，匹配失败后 j 调整为 next[j]，仍会与主串字符不匹配，导致重复回溯。优化思路：若 p[j] == p[next[j]]，则 next[j] = next[next[j]]，直接跳过重复的前缀。

优化后代码

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_M = 10005;
char p[MAX_M];
int next_arr[MAX_M];
int m;

void get_next() {
    int j = 0;
    next_arr[0] = 0;
    for (int i = 1; i < m; ++i) {
        while (j > 0 && p[i] != p[j]) {
            j = next_arr[j - 1];
        }
        if (p[i] == p[j]) {
            j++;
        }
        next_arr[i] = (j > 0 && p[i + 1] == p[j]) ? next_arr[j - 1] : j;
    }
}

int main() {
    cin >> p;
    m = strlen(p);
    get_next();
    for (int i = 0; i < m; ++i) {
        cout << next_arr[i] << " ";
    }
    return 0;
}

四、KMP 匹配流程（一步一步拆解）

有了 next 数组，KMP 匹配流程就非常简单了，核心是 “主串指针不回溯，仅调整模式串指针”。

1. 匹配步骤（0 基）

1. 初始化主串指针 i = 0，模式串指针 j = 0；
2. 遍历主串（i < n）：
   • 若 s[i] == p[j]：i 和 j 同时后移；
   • 若 s[i] != p[j]：
     • 若 j > 0：j = next_arr[j - 1]（回溯到最长相等前缀位置）；
     • 若 j == 0：i 后移（模式串从头开始匹配）；
3. 若 j == m：匹配成功，返回 i - m（主串中模式串的起始索引）；
4. 遍历结束后，若 j != m：匹配失败，返回 -1。

2. 匹配示例（可视化）

• 主串 s = "ABCABCDABABCDABCDABDE"（n=24）
• 模式串 p = "ABCDABD"（m=7）
• next 数组：[0,0,0,0,1,2,0]

匹配过程：

1. i=0, j=0：s[0] = A == p[0] = A → i=1, j=1；
2. 依次匹配 B==B、C==C、D==D、A==A、B==B → i=6, j=6；
3. s[6] = C != p[6] = D：匹配失败，j = next_arr[5] = 2；
4. 此时 s[6] = C == p[2] = C → i=7, j=3；
5. s[7] = D == p[3] = D → j=4，但 s[8] = A != p[4] = A？不，s[8] = A == p[4] = A，继续匹配；
6. 最终 j=7（等于模式串长度），匹配成功，起始索引为 i - m = 15 - 7 = 8（主串中 "ABCDABD" 从索引 8 开始）。

3. 匹配代码

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 1000005;
const int MAX_M = 10005;
char s[MAX_N], p[MAX_M];
int next_arr[MAX_M];
int n, m;

void get_next() {
    int j = 0;
    next_arr[0] = 0;
    for (int i = 1; i < m; ++i) {
        while (j > 0 && p[i] != p[j]) {
            j = next_arr[j - 1];
        }
        if (p[i] == p[j]) {
            j++;
        }
        next_arr[i] = j;
    }
}

int kmp() {
    get_next();
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && s[i] != p[j]) {
            j = next_arr[j - 1];
        }
        if (s[i] == p[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1; 
        }
    }
    return -1; // 匹配失败
}

int main() {
    cin >> s >> p;
    n = strlen(s);
    m = strlen(p);
    int res = kmp();
    if (res != -1) {
        cout << "匹配成功，起始索引：" << res << endl;
    } else {
        cout << "匹配失败" << endl;
    }
    return 0;
}

五、KMP 例题（实战强化）

例题 1：找出主串中所有模式串的出现位置

题目描述：给定主串 s 和模式串 p，找出 p 在 s 中所有出现的起始位置，若未出现则输出 -1。

解题思路：匹配成功后，不直接返回，而是将 j 调整为 next_arr[j-1]，继续匹配后续内容（避免遗漏重叠匹配）。

代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 1000005;
const int MAX_M = 10005;
char s[MAX_N], p[MAX_M];
int next_arr[MAX_M];
int n, m;

void get_next() {
    int j = 0;
    next_arr[0] = 0;
    for (int i = 1; i < m; ++i) {
        while (j > 0 && p[i] != p[j]) {
            j = next_arr[j - 1];
        }
        if (p[i] == p[j]) {
            j++;
        }
        next_arr[i] = j;
    }
}

void kmp() {
    get_next();
    int j = 0;
    bool found = false;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && s[i] != p[j]) {
            j = next_arr[j - 1];
        }
        if (s[i] == p[j]) {
            j++;
        }
        if (j == m) {
            cout << i - m + 1 << " ";
            found = true;
            j = next_arr[j - 1]; // 回溯，继续匹配重叠部分
        }
    }
    if (!found) {
        cout << -1;
    }
    cout << endl;
}

int main() {
    cin >> s >> p;
    n = strlen(s);
    m = strlen(p);
    kmp();
    return 0;
}

例题 2：重复的子字符串（LeetCode 459）

题目描述：给定一个非空字符串 s，判断它是否可以由它的一个子串重复多次构成。例如，s = "abab" 可由 "ab" 重复两次构成，s = "abcabcabc" 可由 "abc" 重复三次构成。

解题思路：利用 next 数组的特性 —— 若 s 可由子串重复构成，则 n % (n - next_arr[n-1]) == 0（n 为 s 长度），且 next_arr[n-1] != 0。

代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 100005;
char s[MAX_N];
int next_arr[MAX_N];
int n;

void get_next() {
    int j = 0;
    next_arr[0] = 0;
    for (int i = 1; i < n; ++i) {
        while (j > 0 && s[i] != s[j]) {
            j = next_arr[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        next_arr[i] = j;
    }
}

bool Substring() {
    get_next();
    int len = n - next_arr[n - 1];
    return next_arr[n - 1] != 0 && n % len == 0;
}

int main() {
    cin >> s;
    n = strlen(s);
    if (Substring()) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    return 0;
}

例题 3：实现 strStr ()（LeetCode 28）

题目描述：实现 strStr() 函数，返回模式串 p 在主串 s 中首次出现的位置，若不存在则返回 -1（与库函数 strstr 功能一致）。

代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 1000005;
const int MAX_M = 10005;
char s[MAX_N], p[MAX_M];
int next_arr[MAX_M];
int n, m;

void get_next() {
    int j = 0;
    next_arr[0] = 0;
    for (int i = 1; i < m; ++i) {
        while (j > 0 && p[i] != p[j]) {
            j = next_arr[j - 1];
        }
        if (p[i] == p[j]) {
            j++;
        }
        next_arr[i] = j;
    }
}

int strStr() {
    if (m == 0) return 0;
    get_next();
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && s[i] != p[j]) {
            j = next_arr[j - 1];
        }
        if (s[i] == p[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

int main() {
    cin >> s >> p;
    n = strlen(s);
    m = strlen(p);
    cout << strStr() << endl;
    return 0;
}

六、KMP 常见误区与注意事项

1. next 数组与模式串绑定：next 数组是模式串的属性，与主串无关，只需构建一次，可复用；
2. 匹配失败时的回溯逻辑：0 基中 j = next_arr[j-1]，1 基中 j = next_arr[j]，切勿混淆；
3. 空模式串处理：若模式串为空，直接返回 0（符合 strstr 函数规范）；
4. 重叠匹配问题：匹配成功后，需将 j 调整为 next_arr[j-1]，而非重置为 0，否则会遗漏重叠的匹配（如 s = "AAAAA"，p = "AA"，需匹配出 0、1、2、3 四个位置）；
5. 字符集问题：若字符串包含大写、数字或特殊字符，无需修改逻辑，直接匹配即可（KMP 与字符集无关）。

七、总结

KMP 算法的核心是 “利用已匹配信息，避免无效回溯”，其精髓在于 next 数组的构建 —— 理解了 “最长相等前后缀”，就理解了 KMP 的本质。

掌握 KMP 的关键步骤：

1. 搞懂暴力匹配的痛点，明确 KMP 的优化思路；
2. 熟练掌握 next 数组的构建（基础版、优化版、0 基 / 1 基转换）；
3. 牢记 KMP 匹配流程，重点是 “主串指针不回溯”；
4. 通过经典例题强化实战，掌握 next 数组的延伸应用（如重复子串判断）。

KMP 作为字符串匹配的基础算法，虽然入门有一定难度，但只要拆解清楚每一步逻辑，多动手实现和调试，就能彻底吃透。学会 KMP 后，再学习 AC 自动机、后缀数组等高级字符串算法，会更加轻松。