深入解析 C++ 中的 KMP 算法：从原理到高效实现

2026-02-01 08:15:44 0条评论 3次阅读 0人点赞

你好！作为一名经常与字符串处理打交道的开发者，我深知在处理海量文本数据时，一个高效的搜索算法能带来多大的性能提升。你可能经历过这样的时刻：当你需要在几百万行的日志文件中查找特定的错误模式时，朴素的暴力搜索算法往往慢得让人难以忍受。这正是我们需要掌握 Knuth-Morris-Pratt (KMP) 算法的原因。

在这篇文章中，我们将一起深入探索 KMP 算法的奥秘。我们不仅要理解“它是怎么工作的”，更要掌握“为什么它比暴力法更快”以及“如何在 C++ 中优雅且高效地实现它”。我们会从最基础的概念入手，逐步剖析算法的核心逻辑，并通过多个实际代码示例来巩固我们的理解。无论你是为了准备技术面试，还是为了优化实际项目中的性能，这篇文章都将为你提供详实的参考。

什么是 KMP 算法？

Knuth-Morris-Pratt 算法（简称 KMP）是一种用于字符串匹配的高效算法，由 Donald Knuth、Vaughan Pratt 和 James H. Morris 在 1977 年共同发表。它的核心思想非常巧妙：利用已经匹配过的信息，避免从头开始进行不必要的比较。

为了更好地理解这一点，让我们先回顾一下简单的暴力匹配法。在暴力法中，如果我们在文本串中匹配模式串时遇到不匹配的字符，我们会将模式串向后移动一位，然后重新从模式串的第一个字符开始比较。这种做法的缺点在于，它丢弃了我们刚刚通过比较获得的“部分匹配”信息。

KMP 算法则不同。它通过预处理模式串，构建一个名为 LPS（Longest Prefix Suffix，最长公共前后缀） 的辅助数组。这个数组告诉我们在发生不匹配时，模式串应该向右滑动多少位，以及模式串的指针应该回退到哪个位置，从而跳过那些注定无法匹配的比较。

核心概念：LPS 数组

LPS 数组是 KMP 算法的灵魂。要理解它，我们首先要搞清楚什么是“最长公共前后缀”。

  • 前缀：除了最后一个字符以外，一个字符串的所有头部组合。
  • 后缀：除了第一个字符以外，一个字符串的所有尾部组合。

例如，对于字符串 "ABABA"：

  • "A" 的前缀和后缀都是空，长度为 0。
  • "AB" 的前缀有 "A"，后缀有 "B"，公共长度为 0。
  • "ABA" 的前缀有 "A", "AB"；后缀有 "BA", "A"。最长的公共部分是 "A"，长度为 1。
  • "ABAB" 的前缀有 "A", "AB", "ABA"；后缀有 "BAB", "AB", "B"。最长的公共部分是 "AB"，长度为 2。

LPS 数组的值正是对应位置的子串中，最长相等前后缀的长度。下面让我们来看看如何为模式串 P = "ABABCABAB" 构建 LPS 数组：

Index (i)

0

1

2

3

4

5

6

7

8

—

—

—

—

—

—

—

—

—

—

Pattern

A

B

A

B

C

A

B

A

B

LPS Value

0

0

1

2

0

1

2

3

4让我们手动模拟一下这个过程（重点关注 i=3 和 i=8）：

  • i=0 (‘A‘): 单个字符，前缀后缀均为空，lps[0] = 0。
  • i=1 (‘B‘): "AB"，无公共前后缀，lps[1] = 0。
  • i=2 (‘A‘): "ABA"，前缀 "A" 与后缀 "A" 匹配，长度为 1，lps[2] = 1。
  • i=3 (‘B‘): "ABAB"，前缀 "AB" 与后缀 "AB" 匹配，长度为 2，lps[3] = 2。
  • i=4 (‘C‘): "ABABC"，前缀 "ABA" 与后缀 "ABC" 不匹配。回退检查，长度变为 0。lps[4] = 0。
  • i=5 (‘A‘): "ABABCA"，前缀 "A" 匹配后缀 "A"。lps[5] = 1。

…

  • i=8 (‘B‘): "ABABCABAB"。其前缀 "ABAB" 与后缀 "ABAB" 完全匹配，长度为 4。所以 lps[8] = 4。

C++ 实现与代码详解

现在，让我们把理论转化为实践。KMP 算法的 C++ 实现主要分为两个函数：INLINECODE726eb4d8（预处理）和 INLINECODE3dca6302（搜索）。

#### 示例 1：标准 KMP 实现（包含详细注释）

这是最经典的实现方式。为了确保代码的健壮性，我们使用 std::vector 来存储结果，避免使用全局变量。同时，我将代码中的关键逻辑进行了详细的中文注释，方便你阅读。

#include 
#include 
#include 

using namespace std;

// 预处理函数：构建 LPS 数组
// pattern: 我们要搜索的模式串
// m: 模式串的长度
// lps: 引用传递的 LPS 数组，用于存储结果
void computeLPSArray(string pattern, int m, vector& lps) {
    int length = 0; // 当前最长公共前后缀的长度
    lps[0] = 0;     // 第一个字符的 LPS 永远是 0
    int i = 1;      // 从模式串的第二个字符开始计算

    // 遍历模式串以填充 LPS 数组
    while (i < m) {
        if (pattern[i] == pattern[length]) {
            // 如果字符匹配，说明我们找到了更长的公共前后缀
            length++;
            lps[i] = length;
            i++;
        }
        else {
            // 如果字符不匹配
            if (length != 0) {
                // 这是一个关键的优化点：
                // 我们不一定要把 length 重置为 0。
                // 我们可以回退到上一个最长前后缀的位置，继续尝试匹配。
                // 类似于搜索时的回退，这保证了我们不会遗漏可能的匹配。
                length = lps[length - 1];
            }
            else {
                // 如果 length 已经是 0，说明当前没有公共前后缀
                lps[i] = 0;
                i++;
            }
        }
    }
}

// KMP 搜索函数
// pattern: 模式串
// text: 文本串
// 返回值: 一个 vector，包含所有匹配成功的起始索引
vector KMPSearch(string pattern, string text) {
    int m = pattern.length();
    int n = text.length();

    // 用于存储结果的数组
    vector result;

    // 创建并初始化 LPS 数组
    vector lps(m);
    computeLPSArray(pattern, m, lps);

    int i = 0; // text 的索引（当前比较位置）
    int j = 0; // pattern 的索引（当前比较位置）

    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }

        // 如果 j 等于 m，说明整个模式串都匹配成功了
        if (j == m) {
            // 记录匹配的起始位置
            result.push_back(i - j);
            
            // 这里的处理非常重要：
            // 即使找到了匹配，我们也可能需要继续搜索。
            // 我们利用 LPS 信息来决定下一次匹配的起始位置，
            // 而不是简单地从头开始。这处理了重叠匹配的情况（例如在 "AAAA" 中搜索 "AA"）。
            j = lps[j - 1];
        }
        // 如果在文本 i 处发生不匹配
        else if (i < n && pattern[j] != text[i]) {
            // 如果 j != 0，说明模式串之前有部分匹配
            // 我们利用 LPS 数组跳过那些肯定匹配不了的字符
            if (j != 0) {
                j = lps[j - 1];
            }
            else {
                // 如果 j == 0，说明模式串第一个字符就不匹配，只能移动文本指针 i
                i++;
            }
        }
    }
    return result;
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";

    vector ans = KMPSearch(pattern, text);

    cout << "Pattern Found at Indexes: ";
    for (auto index : ans)
        cout << index << " ";
    cout << endl;

    return 0;
}

#### 示例 2：处理重叠匹配的场景

在实际开发中，我们经常需要找出所有的匹配项，包括重叠的部分。KMP 算法天生非常适合处理这种情况。让我们看一个经典的例子：在文本 "AAAA" 中查找 "AA"。

  • 暴力法可能会找到索引 0 和 2，而漏掉索引 1（因为它移动步长是 1）。
  • KMP 算法通过 j = lps[j-1] 的回退机制，能够自动处理这种重叠。
#include 
#include 
#include 

using namespace std;

void computeLPSArray(const string& pat, int M, vector& lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void KMPSearchWithOverlap(const string& pat, const string& txt) {
    int M = pat.length();
    int N = txt.length();

    // 创建 LPS 数组
    vector lps(M);
    computeLPSArray(pat, M, lps);

    int i = 0; // txt 的索引
    int j = 0; // pat 的索引
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
        if (j == M) {
            cout << "Found pattern at index " << i - j << endl;
            // 关键：更新 j 以继续查找，包括重叠模式
            j = lps[j - 1];
        } else if (i < N && pat[j] != txt[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i = i + 1;
            }
        }
    }
}

int main() {
    string txt = "AAAA";
    string pat = "AA";
    cout << "Searching for all matches (including overlaps):" << endl;
    KMPSearchWithOverlap(pat, txt);
    return 0;
}

深入理解代码逻辑

让我们再看一下 computeLPSArray 中的这个片段：

if (length != 0) {
    length = lps[length - 1];
}

很多初学者在这里会感到困惑。为什么 INLINECODE3e4f76d9 时，我们不直接把 INLINECODE503f301e 设为 0？

想象一下，我们正在处理模式串 "ABABC…"。当我们处理到 ‘C‘ 时发现不匹配。此时 length 是 2（代表 "AB"）。既然当前字符 ‘C‘ 不匹配，我们想知道：是否存在一个比 "AB" 更短的前缀，它同时也是后缀？

LPS 数组的一个重要性质是：如果当前最长公共前后缀长度为 INLINECODEa7e0167a，那么次长的公共前后缀长度一定是 INLINECODE7dccf052。这种递归结构让我们能够高效地进行回退，而不需要重新遍历字符串。

复杂度分析

我们来分析一下为什么 KMP 算法如此高效。

  • 时间复杂度: O(m + n)

– 构建 LPS 数组：我们需要遍历一次模式串，长度为 m。虽然有内部回退，但每个字符最多被比较几次（指针 i 一直在向前移动，最多增加 m 次）。因此是 O(m)。

– 搜索过程：我们需要遍历一次文本串，长度为 n。在搜索过程中，虽然 i（文本指针）一直向前，但 j（模式串指针）会因为 LPS 而回退。然而，j 的回退次数是受限的，因为 j 的值由 LPS 值决定，且每次回退后至少会匹配一个字符或停止。总体上看，i 和 j 的移动次数与 m + n 成正比。

– 总结：总时间复杂度为线性 O(m + n)。相比于暴力法最坏情况 O(m * n)，这在处理大规模文本时优势巨大。

  • 空间复杂度: O(m)

– 我们需要额外的空间来存储 LPS 数组，其大小等于模式串的长度 m。

实际应用与最佳实践

KMP 算法不仅仅是一个教科书上的算法，它在实际工程中有着广泛的应用。

  • 文本编辑器中的查找功能：当你按下 Ctrl+F 查找单词时，背后的逻辑很可能就用到了类似的优化算法。
  • 入侵检测系统 (IDS)：网络安全设备需要实时扫描网络数据包中的恶意特征码，KMP 的高效性使其成为理想选择。
  • 生物信息学：在 DNA 序列分析中，科学家需要在数以亿计的碱基对中寻找特定的基因序列，KMP 算法提供了一种快速检索的手段。

最佳实践提示：

  • 何时使用：当你需要多次在同一个文本中搜索不同的模式，或者在非常长的流式数据中搜索模式时，KMP 是很好的选择。
  • 何时不需要：如果文本非常短（比如几十个字符），标准库中的 std::string::find 或者简单的暴力法通常更快，因为 KMP 有构建 LPS 数组的额外开销。
  • 中文编码处理：在处理中文等多字节字符时（如 UTF-8），请确保你的逻辑是基于字符或字节的正确理解。通常建议将文本转换为宽字符（wchar_t）或专门处理编码逻辑，避免在半个字符处进行比较，但在纯粹的字节流搜索中，KMP 依然适用。

常见错误与调试技巧

在我编写 KMP 代码的过程中，遇到过不少坑。让我分享几个常见的错误，希望能帮你节省调试时间：

  • 数组越界：最容易犯错的地方是在 INLINECODE5c6772d3 中。当我们执行 INLINECODE4127feb8 时，必须确保 INLINECODEee13c7eb。虽然代码中的 INLINECODE46131b06 保护了这一点，但在手动修改逻辑时要格外小心。
  • LPS 值的理解偏差：LPS[i] 表示的是“长度”，而不是“下一个要比较的索引”。虽然在搜索逻辑中 j = lps[j-1] 直接把长度当作了索引使用，但在概念上要分清。
  • 死循环：在 LPS 计算中，如果逻辑写错（例如忘记 INLINECODE1e10a9a9），程序很容易进入死循环。务必确保每个分支都正确推进了指针 INLINECODEb383a387 或 length。

总结

通过这篇文章，我们一起从零开始构建了 KMP 算法。我们学习了如何通过预处理模式串构建 LPS 数组，以及如何利用它来避免无效的字符比较。虽然 KMP 算法的逻辑比暴力法稍微复杂一点，但它带来的性能提升是显而易见的，尤其是在处理大规模数据时。

我鼓励你亲自敲一遍上面的代码，尝试修改模式串和文本串，观察 LPS 数组的变化，甚至可以尝试用 INLINECODEc0be61f7 打印出每一步的 INLINECODEb42aa51f 和 j 的值，来验证算法的运行轨迹。只有这样，这些理论才能真正变成你自己的技能。

希望这篇文章对你有所帮助！如果你在实现过程中遇到任何问题，或者想讨论更高级的字符串算法（如 Boyer-Moore 或 Rabin-Karp），欢迎随时交流。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/19092.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年