一、算法概述

KMP 算法（Knuth-Morris-Pratt） 是一种高效的单模式串匹配算法，由 Donald Knuth、James H. Morris 和 Vaughan Pratt 于 1977 年联合发表。它能在 O(n + m) 的时间复杂度内，在长度为 n 的主串 text 中找出长度为 m 的模式串 pattern 的所有出现位置。

相比朴素的 O(n × m) 暴力匹配，KMP 的核心改进在于：失配时利用已匹配部分的信息，让模式串智能地跳过不可能匹配的位置，从而避免主串指针回溯。

二、核心思想

2.1 暴力匹配的问题

暴力匹配在失配时，主串指针 i 回退到 i - j + 1（即本轮匹配起点 + 1），模式串指针 j 重置为 0。这导致已匹配的字符被重复比较。

2.2 KMP 的关键洞察

当在 text[i] 和 pattern[j] 处失配时：

  • 我们已经知道 text[i-j ... i-1] 与 pattern[0 ... j-1] 完全匹配（共 j 个字符）
  • 如果我们事先知道 pattern[0 ... j-1] 的最长相等前后缀长度，就可以直接将模式串向右滑动，让前缀对准后缀的位置，继续比较

2.3 next 数组 / 前缀函数

定义 next[j]：pattern[0 ... j-1] 这个子串的最长相等前后缀的长度。即：

  • 前缀：pattern[0 ... k-1]
  • 后缀：pattern[j-k ... j-1]
  • next[j] = 最大的 k（k < j），使得前缀 == 后缀

失配时的操作：j = next[j]，主串指针 i 不动，继续比较 text[i] 和 pattern[j]。

特殊约定：

  • next[0] = -1：当第一个字符就失配时，i 右移，j 重置为 0
  • next[1] = 0：单个字符没有真前后缀

2.4 举例

模式串 "ababaca" 的 next 数组：

j:   0  1  2  3  4  5  6
P:   a  b  a  b  a  c  a
next:-1  0  0  1  2  3  0
  • next[4] = 2："abab" 的最长相等前后缀是 "ab"，长度为 2
  • next[5] = 3："ababa" 的最长相等前后缀是 "aba"，长度为 3

三、算法步骤 / 伪代码

3.1 构建 next 数组

function buildNext(pattern):
    m = length(pattern)
    next = array of size m
    next[0] = -1
    j = 0     // 当前正在计算 next 的位置
    k = -1    // k = next[j-1]，即前一个位置的最长前后缀长度
    
    while j < m - 1:
        if k == -1 or pattern[j] == pattern[k]:
            j = j + 1
            k = k + 1
            next[j] = k       // 或者用优化版：见代码
        else:
            k = next[k]       // 递归回退
    
    return next

3.2 KMP 匹配过程

function KMP(text, pattern):
    n = length(text)
    m = length(pattern)
    next = buildNext(pattern)
    result = empty list
    
    i = 0  // 主串指针
    j = 0  // 模式串指针
    
    while i < n:
        if j == -1 or text[i] == pattern[j]:
            i = i + 1
            j = j + 1
            if j == m:           // 匹配成功
                result.push_back(i - j)
                j = next[j - 1] + 1  // 或 j = next[j-1]; i--, j++ 等价
                // 简化：j = next[j]（需 next[m] = X）
        else:
            j = next[j]          // 失配时模式串跳转
    
    return result

四、C++ 代码实现

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class KMP {
private:
    // ========== 构建 next 数组（未优化版） ==========
    vector<int> buildNext(const string& pattern) {
        int m = pattern.size();
        vector<int> next(m);
        next[0] = -1;
        int j = 0;   // 当前计算位置
        int k = -1;  // 前一个 next 值

        while (j < m - 1) {
            if (k == -1 || pattern[j] == pattern[k]) {
                j++;
                k++;
                // 未优化版：直接赋值
                // next[j] = k;
                // 优化版：避免 pattern[j] == pattern[next[j]] 时的冗余比较
                if (pattern[j] == pattern[k]) {
                    next[j] = next[k];
                } else {
                    next[j] = k;
                }
            } else {
                k = next[k];
            }
        }
        return next;
    }

public:
    // ========== KMP 匹配：返回所有匹配位置的起始下标 ==========
    vector<int> search(const string& text, const string& pattern) {
        vector<int> result;
        int n = text.size();
        int m = pattern.size();
        if (m == 0) return result;

        vector<int> next = buildNext(pattern);

        int i = 0;  // 主串指针
        int j = 0;  // 模式串指针

        while (i < n) {
            if (j == -1 || text[i] == pattern[j]) {
                i++;
                j++;
                if (j == m) {
                    // 匹配成功，记录起始位置
                    result.push_back(i - j);
                    // 继续查找下一个匹配
                    j = next[j - 1] + 1;
                }
            } else {
                j = next[j];
            }
        }
        return result;
    }

    // ========== 获取 next 数组（便于调试/展示） ==========
    vector<int> getNext(const string& pattern) {
        return buildNext(pattern);
    }
};

// ==================== 测试主函数 ====================
int main() {
    KMP kmp;

    // ===== 测试1：基本匹配 =====
    cout << "========== 测试1：基本匹配 ==========" << endl;
    string text1 = "ababcabcabababd";
    string pattern1 = "ababd";
    cout << "主串:     " << text1 << endl;
    cout << "模式串:   " << pattern1 << endl;

    vector<int> pos1 = kmp.search(text1, pattern1);
    cout << "匹配位置: ";
    for (int p : pos1) cout << p << " ";
    cout << endl;
    // 期望: 10

    // ===== 测试2：多次匹配 =====
    cout << "\n========== 测试2：多次匹配 ==========" << endl;
    string text2 = "AAAAA";
    string pattern2 = "AA";
    cout << "主串:     " << text2 << endl;
    cout << "模式串:   " << pattern2 << endl;

    vector<int> pos2 = kmp.search(text2, pattern2);
    cout << "匹配位置: ";
    for (int p : pos2) cout << p << " ";
    cout << endl;
    // 期望: 0 1 2 3

    // ===== 测试3：无匹配 =====
    cout << "\n========== 测试3：无匹配 ==========" << endl;
    string text3 = "abcdef";
    string pattern3 = "xyz";
    cout << "主串:     " << text3 << endl;
    cout << "模式串:   " << pattern3 << endl;

    vector<int> pos3 = kmp.search(text3, pattern3);
    cout << "匹配位置: ";
    if (pos3.empty()) cout << "无匹配";
    for (int p : pos3) cout << p << " ";
    cout << endl;
    // 期望: 无匹配

    // ===== 测试4：LeetCode 28 示例 =====
    cout << "\n========== 测试4：LeetCode 28 示例 ==========" << endl;
    vector<pair<string, string>> testCases = {
        {"sadbutsad", "sad"},
        {"leetcode", "leeto"},
        {"hello", "ll"},
        {"mississippi", "issip"},
        {"a", "a"}
    };

    for (auto& [text, pattern] : testCases) {
        vector<int> pos = kmp.search(text, pattern);
        cout << "text=\"" << text << "\", pattern=\"" << pattern << "\" => ";
        if (pos.empty()) {
            cout << "-1" << endl;
        } else {
            cout << pos[0] << endl;
        }
    }
    // 期望: 0, -1, 2, 4, 0

    // ===== 测试5：展示 next 数组 =====
    cout << "\n========== 测试5：next 数组展示 ==========" << endl;
    string demoPattern = "ababaca";
    vector<int> nextArr = kmp.getNext(demoPattern);
    cout << "模式串: ";
    for (char c : demoPattern) cout << c << "  ";
    cout << endl;
    cout << "索引:   ";
    for (int i = 0; i < (int)demoPattern.size(); i++) cout << i << "  ";
    cout << endl;
    cout << "next:   ";
    for (int v : nextArr) cout << v << "  ";
    cout << endl;
    // 期望: -1  0  0  1  2  3  0

    return 0;
}

五、复杂度分析

步骤 时间复杂度 说明
构建 next 数组 O(m) m 为模式串长度，每个字符最多被回溯访问常数次
KMP 匹配过程 O(n) n 为主串长度，主串指针 i 只增不减
总时间复杂度 O(n + m) 线性时间
空间复杂度 O(m) 仅需存储 next 数组

复杂度证明概要

  • next 构建：变量 j 最多增加 m 次（每次匹配成功 j++），k 的回退次数（k = next[k]）不会超过 j 的增加次数。每个字符平均 O(1)。
  • 匹配过程：主串指针 i 单调递增，最多移动 n 步；模式串指针 j 每次失配回退，但回退总次数不会超过 i 增加的总次数（即 n）。总操作不超过 2n。

与暴力匹配对比

算法 最好情况 最坏情况 空间
暴力匹配 O(n + m) O(n × m) O(1)
KMP O(n + m) O(m)

六、应用场景

场景 说明
文本搜索 / 字符串匹配 在大段文本中查找关键词（Ctrl+F 底层原理）
DNA 序列比对 在基因序列中查找特定基因片段
数据压缩 LZ77 系列压缩算法用 KMP 查找重复子串
入侵检测 网络数据包中检测恶意签名模式
编辑器查找替换 IDE / 文本编辑器中的字符串查找功能
字符串周期与循环节 利用 next 数组求字符串的最小循环节
多模式匹配基础 KMP 的自动机思想延伸出 AC 自动机（多模式匹配）

七、经典例题

LeetCode 28 - 找出字符串中第一个匹配项的下标

题目：给定两个字符串 haystack 和 needle，在 haystack 中找出 needle 出现的第一个位置（下标从 0 开始）。如果不存在，返回 -1。

解题思路：标准的 KMP 单模式匹配。构建 needle 的 next 数组后，在 haystack 中进行匹配，返回第一个匹配位置（或 -1）。

// LeetCode 28 核心代码
int strStr(string haystack, string needle) {
    KMP kmp;
    vector<int> result = kmp.search(haystack, needle);
    return result.empty() ? -1 : result[0];
}

本文第四节的 C++ 代码已完整实现 KMP 算法，可直接处理该题以及所有单模式匹配问题。

核心要点回顾：

  1. next[j] 表示 pattern[0...j-1] 的最长相等前后缀长度
  2. 失配时 j = next[j]，主串指针 i 不回溯
  3. next 构建过程本身也是一个"KMP 匹配"过程（模式串自己匹配自己）
  4. 优化版的 next 避免了 pattern[j] == pattern[next[j]] 时的冗余比较

进一步练习：

  • LeetCode 459：重复的子字符串（利用 next 数组判断周期）
  • LeetCode 686：重复叠加字符串匹配（KMP + 上界分析）
  • LeetCode 214：最短回文串（KMP 求最长回文前缀）
  • LeetCode 1392：最长快乐前缀（直接输出 next 数组的值）
  • AC 自动机（Aho-Corasick）：KMP 在 Trie 上的推广，用于多模式匹配
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 17ms
  4. Powered by Hydro v5.0.1 Community