KMP 字符串匹配：前缀表与高效查找

什么是 KMP 算法

在文本编辑器中查找某个单词、在 DNA 序列中定位特定片段、在代码仓库里搜索关键字……这些场景背后都离不开字符串匹配算法。KMP 算法（Knuth‑Morris‑Pratt）是一种经典的单模式匹配算法，它利用“已部分匹配”这一信息，在不回溯主串指针的前提下高效完成匹配，时间复杂度稳定在 O(n+m)，其中 n 为主串长度，m 为模式串长度。

与朴素的逐位滑动对比不同，KMP 的精髓在于一张被称为**前缀表（next 数组）**的结构。它记录了“当失配发生时，模式串应该跳转到哪里继续比较”，从而避免了大量无意义的重复劳动。

暴力匹配为什么慢

暴力匹配的思路很简单：将模式串与主串从第一个字符开始逐个对齐，一旦字符失配，就把模式串整体右移一位，重新从模式串的开头进行比较。

主串: a b a b c a b a a  
模式: a b a a

• 第一趟：a b a b 匹配，第4位 b ≠ a 失配 → 模式右移1位。
• 第二趟：b ≠ a 立刻失配 → 再右移。
• 第三趟：a b a 匹配，第4位 c ≠ a 失配 → 右移…… 重复的对齐操作让最坏时间复杂度达到 O(n·m)。事实上，失配时我们已经获得了“模式串前几个字符匹配成功”的信息，直接丢弃这些信息是低效的。

KMP 核心思想：跳过失配的无用比较

KMP 利用模式串自身的前后缀相似性来智能跳跃。当模式串的第 j 位与主串的第 i 位失配时：

• 已经匹配的部分 P[0..j-1] 一定是正确的。
• 如果我们能找到一个尽量长的真前缀，它同时是已匹配部分的真后缀，那么就可以把模式串滑动到该前缀与后缀对齐的位置，主串指针 i 不必回退，j 跳到前缀长度所指示的位置继续比较。

举例：模式串 ababa，已匹配部分 abab。它的最长“相等真前缀和真后缀”是 ab（长度2）。失配时，可以直接将 j 回退到索引2（第三个字符），相当于模式串整体向右滑动了 2 位，而主串 i 不变。

这个“最长相等前后缀长度”组成的数组就是前缀表（next 数组）。

前缀表（next 数组）的构建

前缀表 next[j] 的含义：当模式串第 j 个字符失配时，模式串指针应该跳转到的位置（即已匹配部分的最长相等真前后缀长度）。注意这里使用0 索引，next[0] 固定为 -1 或 0 视实现而定，本教程采用常见设置：next[0] = -1 表示第一个字符就失配时，主串 i++ 并且 j 回到 0。

构建 next 数组的过程本身就是一种“模式串自我匹配”的过程。

手工计算思想

对模式串 P = "ababa"，计算每个前缀子串的最长相等前后缀长度：

这样当第 j 位失配，跳转到 next[j] 即可。

编程实现 next 数组

利用递推，设已知 next[0..j-1]，求 next[j]。
令 k = next[j-1]，如果 P[k] == P[j-1]，则 next[j] = k+1；否则递归查找 k = next[k]，直到找到相等或 k == -1。

代码示意（C++版）：

vector<int> getNext(const string& P) {
    int m = P.size();
    vector<int> next(m, -1);
    int k = -1, j = 0;      // k 表示当前最长前后缀长度-1，j是正在计算的索引
    while (j < m - 1) {
        if (k == -1 || P[k] == P[j]) {
            ++k; ++j;
            next[j] = k;    // 注意：j先自增，next[j]赋值
        } else {
            k = next[k];     // 回溯
        }
    }
    return next;
}

常见优化：nextval

当 P[next[j]] == P[j] 时，跳转后字符仍相同，必然继续失配，可以直接将 next[j] 更新为 next[next[j]]，得到nextval 数组，进一步提高效率。初学者可直接使用基础 next，理解优化思想即可。

KMP 匹配过程详解

有了 next 数组，匹配逻辑变得极其简洁：

1. 初始化主串指针 i = 0，模式串指针 j = 0。
2. 当 i < n 且 j < m 时：
   • 若 j == -1 或当前字符匹配（T[i] == P[j]）：i++，j++。
   • 否则失配：j = next[j]（i 不动）。
3. 若 j == m，说明匹配成功，返回 i - j；否则返回 -1。

每轮要么 i 前进，要么 j 利用 next 回退。因为 j 回退的总次数不会超过 i 前进的次数，整体时间复杂度 O(n+m)。

一例走通

主串: ababcabcabababd
模式串: ababd
next 数组（0‑based, -1起始）: [-1, 0, 0, 1, 2]

逐步跟踪：

1. i=0,j=0: a==a → i=1,j=1
2. b==b → i=2,j=2
3. a==a → i=3,j=3
4. b==b → i=4,j=4
5. c≠d → 失配，j=next[4]=2，i保持4
6. j=2 (a) vs i=4 (c) 失配 → j=next[2]=0，i=4
7. j=0 (a) vs i=4 (c) 失配 → j=next[0]=-1，随后进入 if(j==-1) 分支：i=5,j=0
8. 继续匹配……最终在 i=10 处完全匹配。

代码实现（完整版）

C++

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

vector<int> getNext(const string& P) {
    int m = P.size();
    vector<int> next(m, -1);
    int k = -1, j = 0;
    while (j < m - 1) {
        if (k == -1 || P[k] == P[j]) {
            ++k; ++j;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
    return next;
}

int KMP(const string& T, const string& P) {
    int n = T.size(), m = P.size();
    if (m == 0) return 0;
    vector<int> next = getNext(P);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || T[i] == P[j]) {
            ++i; ++j;
        } else {
            j = next[j];
        }
    }
    return (j == m) ? (i - j) : -1;
}

int main() {
    string text = "ababcabcabababd";
    string pattern = "ababd";
    int pos = KMP(text, pattern);
    cout << "匹配位置: " << pos << endl; // 输出 10
    return 0;
}

Python

def get_next(pattern):
    m = len(pattern)
    nxt = [-1] * m
    k, j = -1, 0
    while j < m - 1:
        if k == -1 or pattern[k] == pattern[j]:
            k += 1
            j += 1
            nxt[j] = k
        else:
            k = nxt[k]
    return nxt

def kmp(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0:
        return 0
    nxt = get_next(pattern)
    i = j = 0
    while i < n and j < m:
        if j == -1 or text[i] == pattern[j]:
            i += 1
            j += 1
        else:
            j = nxt[j]
    return i - j if j == m else -1

# 测试
text = "ababcabcabababd"
pattern = "ababd"
print("匹配位置:", kmp(text, pattern))  # 10

复杂度与适用场景

• 时间复杂度：预处理 next 数组 O(m)，匹配过程 O(n)，总 O(n+m)。
• 空间复杂度：O(m)（存储 next 数组）。
• 优点：主串指针不回溯，特别适合流式输入和大文本。
• 缺点：对模式串进行预处理，当模式串较短时优势不明显，但在需要多次使用同一模式匹配多个主串时，预处理成本可摊薄。

总结

KMP 算法的灵魂在于前缀表——它用模式串自身的结构预判了失配后的最优移动距离，使得匹配过程无需回溯主串。掌握 KMP 不仅是学习字符串处理的基础，更是理解“用空间换时间”思想的极佳案例。建议读者亲手模拟一遍 next 数组的生成与一次完整匹配，所有抽象感都将烟消云散。