深入理解KMP算法（C++语言实现高效字符串匹配）

为什么需要KMP算法？

假设我们要在字符串 "ABABABCABABABD" 中查找子串 "ABABABD"。如果使用暴力匹配法，一旦某一位不匹配，就要将模式串整体右移一位，重新从头开始比较。这在最坏情况下效率极低。

而KMP算法的核心思想是：当发生不匹配时，利用已匹配部分的信息，尽可能多地跳过一些字符，避免重复比较。这就依赖于我们预先计算出的 next 数组。

KMP算法的关键：构建next数组

next[i] 表示模式串中前 i 个字符组成的子串的最长相等前后缀的长度。例如，模式串 "ABABABD" 的 next 数组为：

模式串: A B A B A B D索引:   0 1 2 3 4 5 6next:  -1 0 0 1 2 3 4  

注意：有些教材将 next[0] 定义为0，但本文采用更常见的 -1 起始方式，便于统一处理边界。

C++实现KMP算法

下面我们用C++语言完整实现KMP算法，包括 getNext 函数和 kmpSearch 函数。

#include <iostream>#include <vector>#include <string>// 构建next数组std::vector<int> getNext(const std::string& pattern) {    int n = pattern.length();    std::vector<int> next(n);    next[0] = -1;    int i = 0, j = -1;    while (i < n - 1) {        if (j == -1 || pattern[i] == pattern[j]) {            ++i;            ++j;            next[i] = j;        } else {            j = next[j];        }    }    return next;}// KMP搜索函数int kmpSearch(const std::string& text, const std::string& pattern) {    std::vector<int> next = getNext(pattern);    int i = 0, j = 0;    int n = text.length();    int m = pattern.length();    while (i < n && j < m) {        if (j == -1 || text[i] == pattern[j]) {            ++i;            ++j;        } else {            j = next[j];        }    }    if (j == m) {        return i - j; // 返回首次匹配位置    }    return -1; // 未找到}// 测试主函数int main() {    std::string text = "ABABABCABABABD";    std::string pattern = "ABABABD";    int pos = kmpSearch(text, pattern);    if (pos != -1) {        std::cout << "Pattern found at index: " << pos << std::endl;    } else {        std::cout << "Pattern not found." << std::endl;    }    return 0;}  

代码解析

• getNext 函数：使用双指针 i 和 j 遍历模式串，动态构建 next 数组。
• kmpSearch 函数：主串指针 i 不回溯，仅根据 next 数组调整模式串指针 j，实现高效匹配。
• 时间复杂度：构建 next 数组 O(m)，搜索过程 O(n)，总时间复杂度 O(n + m)。

总结

KMP算法是高效字符串搜索的经典代表，广泛应用于文本编辑器、生物信息学（DNA序列比对）、编译器词法分析等领域。掌握其原理和C++字符串匹配实现，不仅能提升编程能力，还能加深对算法设计中“预处理+复用信息”思想的理解。

希望这篇教程能帮助编程小白轻松入门KMP算法！动手敲一遍代码，你会对这个模式匹配算法有更深刻的认识。