#创作计划#KMP算法

飞到绝技

2025-09-18 20:39:38

发布于：江苏

10阅读

0回复

0点赞

目录（Contents）：

第一部分：导言

第二部分：什么是 KMP 算法

第三部分：KMP 算法的核心概念与预处理

第四部分：KMP 算法的匹配过程与实现

第五部分：刷题时光

第六部分：常见踩坑点与避坑指南

第七部分：常见问题与注意事项

第一部分：导言:

在字符串处理场景中，我们经常需要解决 “模式匹配” 问题 —— 比如从一篇文章里找某个关键词、在日志中匹配特定指令，这时候最直接的思路是 “暴力匹配”：用模式串的每个字符依次对比主串的对应位置，不匹配就回溯主串重新开始。

但暴力匹配效率极低，比如主串是"AAAAA...A"（1000 个 A），模式串是"AAAB"，每次匹配到最后一个字符才失败，主串频繁回溯导致时间复杂度达到O(n*m)（n 为主串长度，m 为模式串长度）。

为此，我们需要更高效的算法 ——KMP 算法。它通过预处理模式串生成 “部分匹配表”（PMT），避免主串回溯，将时间复杂度优化到O(n+m)，是字符串匹配的经典高效方案。

第二部分：什么是 KMP 算法：

KMP 算法由 Knuth、Morris 和 Pratt 三位科学家共同提出，核心思想是利用模式串自身的前缀后缀匹配信息，在匹配失败时让模式串 “少后退”，从而跳过不必要的对比步骤。

核心问题：为什么暴力匹配效率低？

假设主串为s = "ABCABDABCAB"，模式串为p = "ABCAB"：

·暴力匹配时，前 4 个字符"ABCA"均匹配，第 5 个字符s[4] = 'D'与p[4] = 'B'不匹配，此时主串会回溯到s[1]，模式串回到p[0]重新开始。

·但观察模式串"ABCAB"，其前 4 个字符"ABCA"的前缀"A"和后缀"A"是最长匹配的（长度 1）。这意味着主串中s[3] = 'A'（对应模式串p[3] = 'A'）其实可以直接与模式串的p[1]继续匹配，无需回溯主串。

第三部分：KMP 算法的核心概念与预处理：

在学习 KMP 的实现前，必须掌握两个核心概念：前缀后缀和部分匹配表（PMT）。

3.1. 前缀与后缀：

·前缀：字符串中除最后一个字符外，所有以第一个字符开头的连续子串。例："ABCAB"的前缀为["A", "AB", "ABC", "ABCA"]。

·后缀：字符串中除第一个字符外，所有以最后一个字符结尾的连续子串。例："ABCAB"的后缀为["B", "AB", "CAB", "BCAB"]。

·最长公共前缀后缀（LCP）：前缀和后缀中长度最长的相同子串。例："ABCAB"的 LCP 为"AB"，长度为 2。

3.2. 部分匹配表（PMT）：

部分匹配表（也称next数组）是 KMP 的核心，它存储了模式串中每个位置的前缀子串的 LCP 长度。

·下标：模式串的字符位置（从 0 开始）。

·值：该位置前的前缀子串（即p[0..i-1]）的 LCP 长度。

如何构建 PMT（以模式串p = "ABCAB"为例）：

模式串字符	p[0] = 'A'	p[1] = 'B'	p[2] = 'C'	p[3] = 'A'	p[4] = 'B'
前缀子串	空串	"A"	"AB"	"ABC"	"ABCA"
LCP 长度	0	0	0	1	2
PMT 值	0	0	0	1	2

构建 PMT 的代码实现：

核心逻辑：用双指针i（指向后缀末尾）和j（指向前缀末尾）遍历模式串，通过对比字符更新 LCP 长度：

#include <vector>
#include <string>
using namespace std;
// 构建模式串a的部分匹配表（b数组）
vector<int> buildPMT(const string& a) {
    int c = a.size();
    vector<int> b(c, 0); // 初始化PMT数组，长度与模式串一致
    int d = 0; // d记录当前LCP的长度（同时指向前缀末尾） 
    for (int i = 1; i < c; i++) { // i从1开始，因为i=0的前缀子串为空
        // 若当前字符不匹配，回溯d到上一个可能的LCP位置
        while (d > 0 && a[i] != a[d]) {
            d = b[d - 1];
        }
        // 若匹配，LCP长度+1
        if (a[i] == a[d]) {
            d++;
        }
        b[i] = d; // 记录当前位置的LCP长度
    }
    return b;
}

第四部分：KMP 算法的匹配过程与实现：

有了 PMT，KMP 的匹配过程就非常清晰了：用两个指针分别遍历主串s和模式串p，匹配失败时通过 PMT 调整模式串指针，主串指针始终不回溯。

匹配步骤

1.初始化主串指针i = 0，模式串指针j = 0，并构建模式串的 PMT。

2.遍历主串：

·若s[i] == p[j]：两个指针同时后移（i++，j++）。

·若s[i] != p[j]：

·若j > 0：通过 PMT 将j调整为pmt[j-1]（利用前缀后缀匹配信息跳过无效对比）。

·若j == 0：主串指针后移（i++），模式串从开头重新匹配。

3.当j == p.size()时，说明模式串完全匹配，返回匹配的起始位置（i - j）；遍历结束未匹配则返回 - 1。

完整代码实现：

#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 构建部分匹配表（PMT）
vector<int> buildPMT(const string& a) {  // a表示模式串
    int b = a.size();                     // b表示模式串长度
    vector<int> c(b, 0);                  // c表示PMT数组
    int d = 0;                            // d记录当前最长公共前缀长度
    for (int i = 1; i < b; i++) {
        while (d > 0 && a[i] != a[d]) {
            d = c[d - 1];
        }
        if (a[i] == a[d]) {
            d++;
        }
        c[i] = d;
    }
    return c;
}
// KMP匹配：返回模式串a在主串s中第一次出现的起始下标，未匹配返回-1
int kmpMatch(const string& s, const string& a) {  // a为模式串
    int e = s.size();                              // e为主串长度
    int b = a.size();                              // b为模式串长度
    if (b == 0) return 0;                          // 模式串为空，默认匹配开头
    vector<int> c = buildPMT(a);                   // c为PMT数组
    int d = 0;                                     // d为模式串指针
    for (int i = 0; i < e; i++) {                  // i为主串指针
        // 匹配失败，调整模式串指针d
        while (d > 0 && s[i] != a[d]) {
            d = c[d - 1];
        }
        // 匹配成功，双指针后移
        if (s[i] == a[d]) {
            d++;
        }
        // 模式串完全匹配，返回起始位置
        if (d == b) {
            return i - d + 1;
        }
    }
    return -1;  // 未找到匹配
}
// 测试示例
int main() {
    string s = "ABCABDABCAB";  // 主串
    string a = "ABCAB";        // 模式串（a表示）
    int pos = kmpMatch(s, a);
    if (pos != -1) {
        cout << "模式串第一次出现的位置：" << pos << endl;  // 输出：0
    } else {
        cout << "未找到模式串" << endl;
    }
    return 0;
}

第五部分：刷题时光：

例题 1：LeetCode 28. 找出字符串中第一个匹配项的下标

题目大意：给你两个字符串haystack（主串）和needle（模式串），请返回needle在haystack中首次出现的下标。如果needle不是haystack的一部分，则返回-1。

解题思路：直接套用 KMP 算法模板，核心是构建 PMT 并执行匹配逻辑。

完整代码：

#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 构建部分匹配表
vector<int> buildPMT(const string& a) {  // a表示模式串(needle)
    int b = a.size();                     // b表示模式串长度
    vector<int> c(b, 0);                  // c表示PMT数组
    int d = 0;                            // d记录当前最长公共前缀长度 
    for (int i = 1; i < b; i++) {
        while (d > 0 && a[i] != a[d]) {
            d = c[d - 1];
        }
        if (a[i] == a[d]) {
            d++;
        }
        c[i] = d;
    }
    return c;
}
// 字符串匹配函数
int strStr(string e, string a) {  // e表示主串(haystack)，a表示模式串(needle)
    int f = e.size();              // f表示主串长度
    int b = a.size();              // b表示模式串长度
    if (b == 0) return 0;          // 模式串为空时返回0
    vector<int> c = buildPMT(a);   // c表示PMT数组
    int d = 0;                     // d为模式串指针
    for (int i = 0; i < f; i++) {  // i为主串指针
        // 匹配失败时回溯模式串指针
        while (d > 0 && e[i] != a[d]) {
            d = c[d - 1];
        }
        // 匹配成功时移动模式串指针
        if (e[i] == a[d]) {
            d++;
        }
        // 完全匹配时返回起始位置
        if (d == b) {
            return i - d + 1;
        }
    }
    return -1;  // 未找到匹配
}
int main() {
    string e, a;  // e为主串，a为模式串
    cin >> e >> a;
    cout << strStr(e, a) << endl;
    return 0;
}

例题 2：查找模式串在主串中的所有匹配位置

题目大意：读入主串s和模式串p，输出p在s中所有出现的起始下标，若未匹配则输出 “无匹配”。

解题思路：在 KMP 匹配中，当j == m（匹配成功）时，不直接返回，而是通过 PMT 调整j（j = pmt[j-1]），继续查找后续匹配。

核心代码片段：

// 查找所有匹配位置，返回下标列表
vector<int> kmpFindAll(const string& a, const string& b) {  // a为主串，b为模式串
    int c = a.size();                                       // c为主串长度
    int d = b.size();                                       // d为模式串长度
    vector<int> e;                                          // e用于存储匹配位置结果
    if (d == 0) return e;
    vector<int> f = buildPMT(b);                            // f为PMT数组
    int g = 0;                                              // g为模式串指针
    for (int i = 0; i < c; i++) {                           // i为主串指针
        while (g > 0 && a[i] != b[g]) {
            g = f[g - 1];
        }
        if (a[i] == b[g]) {
            g++;
        }
        // 匹配成功，记录位置并继续查找
        if (g == d) {
            e.push_back(i - g + 1);
            g = f[g - 1];  // 关键：回溯g以查找下一个匹配
        }
    }
    return e;
}
// 测试
int main() {
    string a = "ABABABABC";  // a为主串
    string b = "ABA";        // b为模式串
    vector<int> h = kmpFindAll(a, b);  // h存储所有匹配位置
    if (h.empty()) {
        cout << "无匹配" << endl;
    } else {
        cout << "所有匹配位置：";
        for (int pos : h) {
            cout << pos << " ";  // 输出：0 2 4
        }
        cout << endl;
    }
    return 0;
}

第六部分：常见踩坑点与避坑指南：

KMP 算法的逻辑看似清晰，但在编码和理解过程中极易陷入细节陷阱，以下是高频踩坑点及解决方法：

1. PMT 构建：用 “if” 代替 “while” 回溯 j，导致 LCP 计算错误：

坑点描述：

构建 PMT 时，当p[i] != p[j]，新手常误用if语句单次回溯j（如if (j>0) j=pmt[j-1]），而非while循环，导致无法找到最长的有效前缀后缀。

反例代码（错误）

// 错误：用if代替while，无法彻底回溯
for (int i = 1; i < m; i++) {
    if (j > 0 && p[i] != p[j]) { 
        j = pmt[j - 1];
    }
    if (p[i] == p[j]) {
        j++;
    }
    pmt[i] = j;
}

问题分析：

以模式串p = "ABABAC"为例：

·当i=4（p[i]='A'）、j=3（p[j]='B'）时，p[i] != p[j]，需回溯j到pmt[2] = 2（p[2]='A'）。此时p[4]='A' == p[2]='A'，j应更新为 3。

·若用if，仅回溯一次就停止；若p[j]仍不匹配（如更复杂的模式串），会导致 LCP 长度计算偏短，后续匹配出错。

避坑方案：

必须用while循环回溯j，直到j=0或p[i] == p[j]，确保找到最长的公共前缀后缀：

while (j > 0 && p[i] != p[j]) {
    j = pmt[j - 1];
}

2. 匹配时：主串指针回溯，违背 KMP 核心逻辑：

坑点描述：

受暴力匹配思维影响，在s[i] != p[j]时，不自觉地让主串指针i回溯（如i = i - j + 1），导致时间复杂度退化为O(n*m)，失去 KMP 的效率优势。

反例代码（错误）

// 错误：主串指针i回溯，等同于暴力匹配
for (int i = 0; i < n; i++) {
    while (j > 0 && s[i] != p[j]) {
        j = pmt[j - 1];
        i++; // 多余的主串回溯，完全错误
    }
    // ...
}

问题分析：

KMP 的核心优化是 “主串不回溯”，所有调整仅针对模式串指针j。主串指针i一旦后移，就不再退回，这是保证O(n+m)复杂度的关键。

避坑方案：

牢记：匹配过程中主串指针i只做自增，绝不回溯。所有匹配失败的调整都通过修改j实现。

3. 边界处理：忽略模式串为空或长度大于主串的情况

坑点描述：

编码时未考虑极端边界场景，如模式串p为空、p.size() > s.size()，导致数组越界或返回错误结果。

反例代码（错误）

// 错误：未处理边界，p为空时pmt构建会出错
int kmpMatch(const string& s, const string& p) {
    int n = s.size();
    int m = p.size();
    vector<int> pmt = buildPMT(p); // p为空时，buildPMT会创建空