KMP算法详解（C++实现与原理剖析）

KMP 的关键：前缀函数（Partial Match Table）

前缀函数（也叫 next 数组）是 KMP 算法的核心。它记录了模式串中每个位置的最长相同前后缀长度。

例如，模式串 "ABABABD" 的前缀函数如下：

• 位置 0（'A'）：无前后缀 → 0
• 位置 1（'B'）：前缀 "A"，后缀 "B" → 0
• 位置 2（'A'）：前缀 "AB"，后缀 "BA" → 最长公共为 "A" → 长度 1
• 位置 3（'B'）：前缀 "ABA"，后缀 "BAB" → 最长公共为 "AB" → 长度 2
• ……以此类推

这个数组告诉我们在匹配失败时，模式串应该“跳”到哪里继续匹配，而不需要回退主串指针。

C++ 实现步骤

我们将分两步实现 KMP：

1. 构建模式串的前缀函数（next 数组）
2. 使用 next 数组进行主串匹配

第一步：构建 next 数组

void computeLPSArray(const std::string& pattern, std::vector<int>& lps) {    int len = 0; // 当前最长前缀后缀长度    lps[0] = 0; // 第一个字符的 lps 值为 0    int i = 1;    while (i < pattern.length()) {        if (pattern[i] == pattern[len]) {            len++;            lps[i] = len;            i++;        } else {            if (len != 0) {                len = lps[len - 1]; // 回退            } else {                lps[i] = 0;                i++;            }        }    }}

第二步：KMP 搜索函数

int KMPSearch(const std::string& text, const std::string& pattern) {    int n = text.length();    int m = pattern.length();    if (m == 0) return 0;    std::vector<int> lps(m, 0);    computeLPSArray(pattern, lps);    int i = 0; // text 的索引    int j = 0; // pattern 的索引    while (i < n) {        if (pattern[j] == text[i]) {            i++;            j++;        }        if (j == m) {            // 找到匹配，返回起始位置            return i - j;            // 如果要找所有匹配，可改为：std::cout << "Found at " << i - j << std::endl; j = lps[j - 1];        } else if (i < n && pattern[j] != text[i]) {            if (j != 0)                j = lps[j - 1];            else                i++;        }    }    return -1; // 未找到}

完整示例与测试

#include <iostream>#include <vector>#include <string>// 上面定义的 computeLPSArray 和 KMPSearch 函数放在这里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;}

总结

KMP 算法通过预处理模式串生成前缀函数，实现了在匹配失败时智能跳转，避免了主串指针回退，从而将时间复杂度优化到线性级别。掌握 KMP 不仅有助于解决实际的C++字符串匹配问题，也是理解更高级字符串算法（如 Z 算法、AC 自动机）的基础。

无论你是准备面试，还是学习算法设计，KMP 都是一个值得深入理解的经典模式匹配算法。希望这篇教程能帮助你从零开始掌握它！