KMP算法：让字符串匹配不再“从头再来”

你有没有在语文课本里玩过“找相同字”的游戏？比如在一大段文字里找出所有“学习”两个字。如果从头一个个对比，遇到不匹配就退回去重新开始，效率非常低。KMP算法就是帮你“聪明”地跳过已经比对过的部分，像记笔记一样记住哪些地方不需要再比较。

KMP是三位计算机科学家Knuth、Morris、Pratt名字的缩写。它的核心是一个叫“next数组”（也叫部分匹配表）的辅助工具。有了它，当匹配失败时，模式串不会只向右移动1位，而是能一下子跳过多位，大大加快速度。

1. 核心思想：利用模式串自己的“对称性”

什么是前后缀？

假设你的书包里有几本同样的作业本，封面都是“张三”。你想在书架上找一本叫《张三日记》的书，但书只有“张三”两个字。你每次拿着“张三”这两个字去比对书架上的书名。

前缀：字符串从开头截取的一段（不包括最后一个字符本身）。
比如“ABAB”的前缀有：""（空串）、"A"、"AB"、"ABA"（不包括最后一个'B'）。
后缀：字符串从结尾往前截取的一段（不包括第一个字符本身）。
“ABAB”的后缀有：""、"B"、"AB"、"BAB"。
最长公共前后缀：既是前缀又是后缀的最长的那一段。
“ABAB”中，公共的有""和"AB"，最长是"AB"，长度2。

next数组具体存什么？

对于模式串（你要找的字符串）的每个位置 i（从0开始），next[i] 表示：
模式串中从开头到位置 i 的这个子串，它的最长公共前后缀的长度（注意整个子串本身不算，所以长度一定小于 i+1）。

例如模式串 "ABAB"：

next[0]（子串"A"）：没有非空前缀后缀，长度0。
next[1]（子串"AB"）：前缀"A"、后缀"B"，无公共，长度0。
next[2]（子串"ABA"）：前缀有"A"、"AB"；后缀有"A"、"BA"，公共" A"长度1。
next[3]（子串"ABAB"）：前缀" A、AB、ABA"；后缀" B、AB、BAB"，公共"AB"长度2。

所以 next = [0, 0, 1, 2]。

为什么它能加速匹配？

想象你正在玩“拼图”：文本串是长跑道，模式串是一段轨道。暴力匹配就像每次轨道对不准就退后一格重新对齐；而KMP利用轨道自身的对称性（前后缀相同），当失配时，直接让轨道向右滑动，使已匹配部分的后缀与模式串的前缀对齐。

我们画个示意图：

文本 T：A B A B A B A B
模式 P：A B A B C

第一次比对到位置4（下标从0开始）：

T: A B A B A B A B
P: A B A B C
   ↑       ↑  ↑
   i=0    i=4 失配

此时P[4]=C与T[4]=A不同。但前面已匹配了"ABAB"，它的最长公共前后缀是"AB"（长度2）。所以我们可以将模式串向右移动，使得P[2]（即next[4]=2）与T[4]对齐，然后继续比：

T: A B A B A B A B
P:     A B A B C
       ↑ (P[2] = A 与 T[4] = A 匹配)

省去了从P[0]重新开始比较的2步。

2. 如何构建next数组（递推思想）

构建next数组就像在模式串内部玩一次“自我匹配”。我们用两个指针：i 遍历模式串的每个位置（从1开始），j 记录当前已经匹配的前缀长度。

步骤（经典实现，next[i]表示最长公共前后缀长度，失配时用next[i-1]回退）：

初始化 next[0]=0，i=1，j=0。
如果 P[i] == P[j]，说明可以延长公共前后缀，则 next[i]=j+1，i++，j++。
否则，如果 j>0，就让 j 回退到 next[j-1]（因为前面可能有更短的公共前后缀），然后重新比较 P[i] 与 P[j]。
如果 j==0，说明没有公共前后缀，next[i]=0，i++。

这个过程有点像你在做“找相同”游戏：从开头开始，一边走一边记下哪些部分已经匹配过。

举例：模式串 "ABCDABD"

i	子串	最长公共前后缀	next[i]
0	A	无	0
1	AB	无	0
2	ABC	无	0
3	ABCD	无	0
4	ABCDA	"A"长度1	1
5	ABCDAB	"AB"长度2	2
6	ABCDABD	无（因为前缀"ABCDAB"与后缀"BCDABD"不同）	0

注意：当 i=6 时，P[6]='D' ≠ P[j]=P[2]='C'，j 从2回退到 next[1]=0，发现仍不同，所以 next[6]=0。

3. 匹配过程：文本指针永不回溯

有了next数组，匹配过程与构建next非常相似：

用 i 指向文本，j 指向模式串。
若 text[i] == pattern[j]，则 i++，j++。
若不等，则 j = next[j-1]（如果 j>0）；否则 i++。
当 j 等于模式串长度时，说明找到一个匹配位置，记录 i-m+1，然后 j = next[j-1] 继续找下一个。

关键点：文本指针 i 只会向右移动，从不回头。这就是KMP线性时间的原因。

4. 新手容易犯的错误

next数组下标混淆：有的教材把next[i]定义为“失配时应跳到的位置”，而这里我们定义为“最长公共前后缀长度”，使用时需要写成next[j-1]。一定要清楚自己用的是哪种定义。
边界条件：模式串长度为0或1时，需要特殊处理。例如，长度为1时next[0]=0。
while循环的顺序：在构建next时，一定要先处理不相等的情况（while循环），再处理相等的情况，否则可能漏掉匹配。
忘记检查空模式串：KMP搜索函数开头应该判断pattern是否为空，否则会造成数组越界。
找所有匹配时：匹配成功后，不能直接让j=0，而要利用next[j-1]继续，否则会漏掉重叠的匹配（比如在"AAAA"中找"AA"）。

5. 完整可运行的代码示例

C++版（含详细注释）

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

using namespace std;

// 构建next数组，next[i]表示子串P[0..i]的最长公共前后缀长度
vector<int> buildNext(const string &pattern) {
    int m = pattern.size();
    vector<int> next(m, 0); // 初始化全部为0
    int j = 0; // 当前匹配的前缀长度
    for (int i = 1; i < m; i++) {
        // 当j>0且当前字符不匹配，回退j
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j-1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

// KMP匹配，返回所有匹配的起始下标
vector<int> kmpSearch(const string &text, const string &pattern) {
    vector<int> positions; // 存储匹配位置
    if (pattern.empty()) return positions; // 空模式串直接返回
    vector<int> next = buildNext(pattern);
    int n = text.size(), m = pattern.size();
    int j = 0; // 模式串当前比较位置
    for (int i = 0; i < n; i++) {
        // 字符不匹配，利用next调整j
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j-1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == m) {
            positions.push_back(i - m + 1); // 记录匹配起始位置
            j = next[j-1]; // 继续寻找下一个匹配
        }
    }
    return positions;
}

int main() {
    string text = "ABABABAB";
    string pattern = "ABAB";
    vector<int> pos = kmpSearch(text, pattern);
    cout << "模式串出现位置: ";
    for (int p : pos) cout << p << " ";
    cout << endl;
    // 显示next数组
    vector<int> nxt = buildNext(pattern);
    cout << "next数组: ";
    for (int x : nxt) cout << x << " ";
    cout << endl;
    return 0;
}

Python版（同样易懂）

def build_next(pattern):
    """构建next数组，返回列表"""
    m = len(pattern)
    next_arr = [0] * m  # 全部初始化为0
    j = 0  # 当前匹配的前缀长度
    for i in range(1, m):
        # 当j>0且字符不相等，回退j
        while j > 0 and pattern[i] != pattern[j]:
            j = next_arr[j-1]
        if pattern[i] == pattern[j]:
            j += 1
        next_arr[i] = j
    return next_arr

def kmp_search(text, pattern):
    """返回模式串在文本中所有出现起始位置"""
    if not pattern:
        return []
    next_arr = build_next(pattern)
    n, m = len(text), len(pattern)
    j = 0  # 模式串当前比较位置
    positions = []  # 存储匹配位置
    for i in range(n):
        # 字符不匹配，回退j
        while j > 0 and text[i] != pattern[j]:
            j = next_arr[j-1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            positions.append(i - m + 1)
            j = next_arr[j-1]  # 继续找下一个
    return positions

# 测试
text = "ABABABAB"
pattern = "ABAB"
pos = kmp_search(text, pattern)
print("模式串出现位置:", pos)
print("next数组:", build_next(pattern))

6. 总结与拓展

KMP把匹配时间从O(n×m)降到O(n+m)，n是文本长度，m是模式串长度。文本指针永不回溯，模式串跳跃移动。
生活例子：就像你查字典找“苹果”这个词，你不需要每次翻到第一页；KMP会记住前面已经看过的字母位置，直接跳到可能匹配的地方。
常见场景：文本编辑器中的查找功能、DNA序列比对、垃圾邮件过滤中的关键词检测等。
进阶知识点：
- 字符串最小周期：利用next数组的最后一个值可以求字符串的最小周期。例如模式串"ABABAB"，next[5]=4，最小周期长度 = m - next[m-1] = 2。
- Z算法：另一种线性时间字符串匹配算法，思想类似但更直观。
- 扩展KMP（Z函数）：可以求出文本串每个位置与模式串的最长公共前缀长度。

想要更深入理解，可以亲手画几遍匹配过程，或尝试用KMP解决一道oj题目（如“剪花布条”）。记住，先掌握朴素匹配，再理解KMP，你会发现它就像一把“剪刀”，能精准地剪掉不必要的比较。

KMP算法与next数组：字符串匹配的加速器