常见算法-KMP

KMP 字符串匹配算法详解：从原理到实现

深入理解 KMP 算法的核心思想，掌握高效字符串匹配的关键技术

---

引言

KMP（Knuth-Morris-Pratt）算法是计算机科学中最经典的字符串匹配算法之一，由 Donald Knuth、Vaughan Pratt 和 James H. Morris 在 1977 年共同发明。该算法通过预处理模式串，避免了暴力匹配中的重复比较，将时间复杂度从 O(m×n) 优化到 O(m+n)。

适用场景：

• 文本编辑器的查找功能
• DNA 序列匹配
• 网络数据包检测
• 编译器词法分析

---

问题背景

字符串匹配问题定义

给定两个字符串：

• 主串（文本串）：需要被搜索的字符串，长度为 n
• 模式串（模板串）：要查找的子串，长度为 m

目标：在主串中找到第一次出现模式串的位置。

主串：  ABABDABACDABABCABAB
模式串：      ABABCABAB

---

暴力匹配的局限性

暴力算法流程

int bruteForce(const string& text, const string& pattern) {
    int n = text.size();
    int m = pattern.size();
    
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) {
            j++;
        }
        if (j == m) return i;  // 找到匹配
    }
    return -1;  // 未找到
}

暴力匹配的问题

主串：  A B A B A B C
模式串：A B A B C

步骤1：  A B A B A B C
        A B A B C
        ✓ ✓ ✓ ✓ ✗ (第5位失配)

步骤2：  A B A B A B C
          A B A B C
          ✗ (第1位就失配，浪费！)

步骤3：  A B A B A B C
            A B A B C
            ✓ ✓ ✓ ✓ ✓ (成功)

问题：失配后，模式串从头开始，主串回退，导致重复比较。

graph TD
    A[主串位置 i] --> B{text i == pattern j?}
    B -->|是| C[i++, j++]
    B -->|否| D[i 回退到 i-j+1]
    D --> E[j 重置为 0]
    E --> F[重新匹配]

时间复杂度：O(m×n)，最坏情况下每个位置都要尝试完整匹配。

---

KMP 核心思想

关键洞察

当失配发生时，我们已经知道了前面已经匹配的部分，可以利用这些信息避免回退。

主串：  A B A B A B C
模式串：A B A B C
        ✓ ✓ ✓ ✓ ✗

已知：前4个字符 "ABAB" 已匹配
观察：模式串的前缀 "AB" 等于已匹配部分的后缀 "AB"
结论：可以直接将模式串滑动到对齐位置，无需回退主串指针

KMP 的两大创新

1. 主串指针不回退：i 只向前移动，永不后退
2. 模式串智能跳转：通过 next 数组确定失配后模式串应该跳到哪里

graph LR
    A[失配发生] --> B[查询 next 数组]
    B --> C[模式串跳转]
    C --> D[继续匹配]
    D --> E{匹配成功?}
    E -->|是| F[完成]
    E -->|否| B

---

Next 数组详解

Next 数组的定义

next[i] 表示：模式串中以位置 i 结尾的子串的最长相等前后缀的长度。

模式串：A B A B C A B A B
索引：  0 1 2 3 4 5 6 7 8
next：  0 0 1 2 0 1 2 3 4

解释：

• next[0] = 0：单个字符没有前后缀
• next[1] = 0：AB 没有相等的前后缀
• next[2] = 1：ABA 的最长相等前后缀是 A（长度1）
• next[3] = 2：ABAB 的最长相等前后缀是 AB（长度2）
• next[4] = 0：ABABC 没有相等的前后缀
• next[7] = 3：ABABCAB 的最长相等前后缀是 AB（长度2）… 等等

前缀和后缀的概念

字符串：A B C D

前缀：A, AB, ABC     (不包含最后一个字符)
后缀：D, CD, BCD     (不包含第一个字符)

Next 数组的构建

核心思想：利用已经计算出的 next 值来计算新的值（动态规划思想）。

vector<int> buildNext(const string& pattern) {
    int n = pattern.size();
    vector<int> next(n);
    next[0] = 0;  // 第一个字符的 next 值为 0
    
    int j = 0;  // j 表示当前最长相等前后缀的长度
    
    for (int i = 1; i < n; i++) {
        // 如果不匹配，回退 j
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        
        // 如果匹配，增加前后缀长度
        if (pattern[i] == pattern[j]) {
            j++;
        }
        
        next[i] = j;
    }
    
    return next;
}

构建过程示例

模式串：ABABCABAB

i=0: pattern[0]='A'
     next[0] = 0

i=1: pattern[1]='B', pattern[0]='A'
     不匹配，j=0
     next[1] = 0

i=2: pattern[2]='A', pattern[0]='A'
     匹配！j=1
     next[2] = 1

i=3: pattern[3]='B', pattern[1]='B'
     匹配！j=2
     next[3] = 2

i=4: pattern[4]='C', pattern[2]='A'
     不匹配，j回退到next[1]=0
     pattern[4]='C', pattern[0]='A'
     不匹配，j=0
     next[4] = 0

i=5: pattern[5]='A', pattern[0]='A'
     匹配！j=1
     next[5] = 1

... (以此类推)

最终结果：

索引	0	1	2	3	4	5	6	7	8
字符	A	B	A	B	C	A	B	A	B
next	0	0	1	2	0	1	2	3	4

graph TD
    A[开始: i=1, j=0] --> B{pattern i == pattern j?}
    B -->|是| C[j++]
    C --> D[next i = j]
    D --> E[i++]
    
    B -->|否| F{j > 0?}
    F -->|是| G[j = next j-1]
    G --> B
    F -->|否| H[next i = 0]
    H --> E
    
    E --> I{i < n?}
    I -->|是| B
    I -->|否| J[完成]

---

算法实现

完整实现

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class KMP {
public:
    // 构建 next 数组
    vector<int> buildNext(const string& pattern) {
        int n = pattern.size();
        vector<int> next(n);
        if (n == 0) return next;
        
        next[0] = 0;
        int j = 0;
        
        for (int i = 1; i < n; i++) {
            // 失配时回退
            while (j > 0 && pattern[i] != pattern[j]) {
                j = next[j - 1];
            }
            
            // 匹配时前进
            if (pattern[i] == pattern[j]) {
                j++;
            }
            
            next[i] = j;
        }
        
        return next;
    }
    
    // KMP 搜索
    int search(const string& text, const string& pattern) {
        int n = text.size();
        int m = pattern.size();
        
        if (m == 0) return 0;
        if (n < m) return -1;
        
        vector<int> next = buildNext(pattern);
        int j = 0;  // 模式串指针
        
        for (int i = 0; i < n; i++) {  // 主串指针
            // 失配时，模式串回退
            while (j > 0 && text[i] != pattern[j]) {
                j = next[j - 1];
            }
            
            // 匹配时，模式串前进
            if (text[i] == pattern[j]) {
                j++;
            }
            
            // 完全匹配
            if (j == m) {
                return i - m + 1;  // 返回起始位置
            }
        }
        
        return -1;  // 未找到
    }
};

int main() {
    KMP kmp;
    
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    
    int pos = kmp.search(text, pattern);
    
    if (pos != -1) {
        cout << "在位置 " << pos << " 找到模式串" << endl;
        cout << "主串：" << text << endl;
        cout << "匹配：" << string(pos, ' ') << pattern << endl;
    } else {
        cout << "未找到模式串" << endl;
    }
    
    return 0;
}

输出：

在位置 10 找到模式串
主串：ABABDABACDABABCABAB
匹配：          ABABCABAB

---

复杂度分析

时间复杂度

1. 构建 next 数组：O(m)

   • 外层循环：遍历模式串 m 个字符
   • 内层 while 循环：j 最多回退 m 次（均摊分析）

2. 匹配过程：O(n)

   • 外层循环：遍历主串 n 个字符
   • 内层 while 循环：j 最多回退 n 次（均摊分析）

总时间复杂度：O(m + n)

空间复杂度

O(m)：需要存储 next 数组。

与暴力算法对比

算法	时间复杂度	空间复杂度	主串指针
暴力匹配	O(m×n)	O(1)	会回退
KMP	O(m+n)	O(m)	不回退

性能提升：

对于长度为 1000 的主串和长度为 100 的模式串：

• 暴力：最坏 100,000 次比较
• KMP：最多 1,100 次比较

---

总结

核心要点

1. KMP 的本质：利用已匹配信息，避免无效回退
2. Next 数组：记录最长相等前后缀，是算法的核心
3. 时间复杂度：O(m+n)，主串指针不回退
4. 适用场景：单模式串匹配，需要高效查找

优缺点对比

优点：

• ✓ 时间复杂度优秀：O(m+n)
• ✓ 主串指针不回退，适合流式处理
• ✓ 易于理解和实现

缺点：

• ✗ 需要额外空间：O(m)
• ✗ 多模式匹配需要多次调用
• ✗ 对于短模式串，可能不如暴力快（常数因子）

与其他算法对比

算法	时间复杂度	空间复杂度	适用场景
暴力	O(m×n)	O(1)	短串、简单场景
KMP	O(m+n)	O(m)	单模式、长串
BM	O(n/m)	O(m)	长模式串
AC自动机	O(n+m+k)	O(m×字符集)	多模式匹配

扩展阅读

• KMP 算法原始论文
• Boyer-Moore 算法
• Aho-Corasick 自动机（多模式匹配）
• Sunday 算法