CC++ & Algorithm

KMP字符串匹配 —— 像侦探一样快速找线索

困难5
语言版本：C++
概述：用“失配时的线索”代替暴力重头查找，让匹配速度大大提升。

KMP字符串匹配 —— 像侦探一样快速找线索

你有没有玩过“找单词”游戏？在一大段文字里，找出一个特定的单词。比如，在一本厚厚的《哈利·波特》里找到“魔法石”这三个字。最笨的办法是从第一个字开始，一个个往后看，如果发现不对，就退回到下一个字重新开始。这种方法很慢，特别是当你找的单词很长的时候，比如找“魁地奇世界杯决赛”，得反复往回退，耗时很久。

KMP算法（由Knuth、Morris、Pratt三位科学家发明）就像一个聪明的侦探：它不会每次失败都从头开始，而是利用已经看过的“线索”（也就是已经匹配的部分）直接跳到可能成功的位置。这个线索叫做 next数组（也叫前缀函数），它告诉我们：当匹配到一半失败时，可以跳过多少个字符继续匹配，从而避免大量无意义的回退。

暴力匹配 —— 最笨但最容易理解的方法

先看看暴力匹配是怎么做的。假设我们有一篇文本（text）和一个模式串（pattern，也就是要找的单词）。暴力匹配从文本的每个位置开始，逐个字符对比模式串：

  • 如果第一个字符就不同，直接跳到文本的下一个位置。
  • 如果匹配到一半失败，模式串的指针回到开头，文本的指针回到刚才匹配起始位置的下一个。

例如，文本 "ABCABCABC"，模式串 "ABCABD"。从文本位置0开始匹配：前5个字符 ABCAB 都相同，第6个字符文本是 C，模式是 D，匹配失败。暴力法会退回到文本位置1（即第二个字符 B），重新从模式串的第一个字符 A 开始比对……重复这个过程很慢，因为很多信息在第一次匹配时已经看过了，但暴力法把它扔掉了。

时间复杂度：最坏情况下文本长度n，模式长度m，暴力法需要比较 O(n*m) 次。当n和m都很大时，比如几百万个字符，速度慢得无法接受。

KMP的核心思想 —— 不浪费已匹配的部分

KMP算法的高明之处在于：当匹配失败时，我们已经知道模式串前面一部分和文本已经相同了。这些相同部分里，可能潜藏着“模式串的前缀等于后缀”的规律。利用这个规律，我们可以把模式串整体向右滑动一段距离，而不是只滑动1个字符。

生活中的类比：拼字游戏

想象你在玩一个拼字游戏，桌面上摆着 ABCDABE 这一串字母，你想拼出 ABCDABD。你从左边开始拼，拼到第7个字母时发现最后一个字母 E 和 D 不匹配。这时，你不需要从头开始，因为刚才拼出的 ABCDAB 中，末尾的 AB 和开头的 AB 是一样的。于是你可以把整个拼板向右移动，让新来的 AB 对准已经存在的 AB，然后从后面继续拼。这样你一下子就跳过了2个字母！（具体跳多少由next数组告诉你）

next数组 —— 模式串的“自我认知”

next数组是KMP的关键，它只跟模式串有关，跟文本无关。next[i] 表示 模式串中，以第i个字符结尾的子串，最长的相等前缀和后缀的长度。看不懂？没关系，我们用例子一步步算。

假设模式串 "ABCDABD"（注意，这里为了方便演示，用字母表示字符，实际可以是任何字符）。我们定义next数组的长度和模式串一样，初始全为0。然后我们让模式串自己和自己比较（相当于一个指针i遍历后缀，指针j遍历前缀）：

  • i = 1（第二个字符 B）：比较 pattern[1] 和 pattern[0]？B != A，next[1] = 0。
  • i = 2（第三个字符 C）：pattern[2] 和 pattern[0] 比，C != A，next[2] = 0。
  • i = 3（第四个字符 D）：D != A，next[3] = 0。
  • i = 4（第五个字符 A）：A == pattern[0]（A），所以 j=1，next[4] = 1。这意味着前5个字符 ABCDA 中，最长的相同前后缀长度是1（前缀 A 和后缀 A）。
  • i = 5（第六个字符 B）：此时 j=1，pattern[5] 和 pattern[1] 比，B == B，j=2，next[5]=2。前6个字符 ABCDAB 中，最长的相同前后缀是 AB（长度2）。
  • i = 6（第七个字符 D）：j=2，pattern[6] 和 pattern[2] 比，D != C，此时需要回退 j = next[1] = 0（因为 next[1]=0，回退到0），然后再次比较 pattern[6] 和 pattern[0]？D != A，所以 next[6]=0。

最终得到 next = [0, 0, 0, 0, 1, 2, 0]。它的含义是：当匹配到模式串的第 i 个字符（索引从0开始）失败时，模式串应该回退到 next[i-1] 的位置继续匹配（注意是 i-1，因为失败发生在 i 处，而已经匹配的部分是 pattern[0..i-1]）。

注意：在实际代码中，next数组通常这样定义：next[j] 表示当模式串第 j 个字符匹配失败后，模式串指针应该跳转到的位置（即 next[j] 是前面已经匹配的部分中，最长的前缀长度）。有些版本next数组有偏移，但原理一样。

用next数组加速匹配过程

有了next数组，匹配过程就变成了侦探破案。我们有两个指针：i 指向文本，j 指向模式串。开始时 i=0, j=0。

  • 如果 text[i] == pattern[j]，两个指针都前进（i++, j++）。
  • 如果 text[i] != pattern[j]：
    • 如果 j>0，说明前面部分已经匹配，我们可以利用 next[j-1] 跳过一部分，让 j = next[j-1]（模式串向右滑动）。
    • 如果 j==0，说明模式串第一个字符就不匹配，那只能 i++，继续比较下一个文本字符。
  • 当 j == m（模式串长度）时，就找到了一个匹配。此时输出匹配起始位置（i - m），然后继续找后面的匹配：让 j = next[m-1]（相当于模式串向右滑动，文本指针继续前进）。

还是用文本 "ABCABCABC" 找模式串 "ABCABC" 为例（模式串长度6，next数组？我们先算一下：ABCABC 的 next 为 [0,0,0,1,2,3]？实际上：

  • i=1('B') ≠ 'A' →0
  • i=2('C') ≠ 'A' →0
  • i=3('A') == 'A' →1
  • i=4('B') == pattern1 →2
  • i=5('C') == pattern2 →3 所以 next = [0,0,0,1,2,3]。

匹配过程：

  • i=0~5: 文本 ABCABC 和模式 ABCABC 完全匹配，j 从0增加到6，当 j==6时输出位置0。然后 j = next[5] = 3，即模式串的前3个字符 ABC 已经和文本的后3个 ABC 匹配，所以文本指针 i=5（已经指向最后一个C），j=3，继续比较。
  • 接下来 i=6（文本第7个字符 A），j=3（模式第4个字符 A）？不对，i从5后继续，实际上文本指针i已经移动到6，i=6对应文本的第七个字符A（索引从0开始，文本索引6是第七个字符？原文文本是 "ABCABCABC"，索引0='A',1='B',2='C',3='A',4='B',5='C',6='A',7='B',8='C'）。当 j=3时，比较 text[6]='A' 和 pattern[3]='A'，相等，j=4；接着 text[7]='B' 和 pattern[4]='B'，j=5；text[8]='C' 和 pattern[5]='C'，j=6。再次找到匹配，输出位置3（8-5=3？注意公式 i-m+1 = 8-6+1=3）。完美！

代码实现（带详细注释）

下面是一个完整的C++代码，实现了KMP算法。我们添加了中文注释，方便理解。

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

// 生成长度为模式串长度的next数组
// next[j] 表示当模式串第j个字符匹配失败时，模式串应该回退到的位置（即已匹配部分的最长相同前缀后缀长度）
vector<int> getNext(const string& pattern) {
    int m = pattern.size();          // 模式串长度
    vector<int> next(m, 0);          // next数组，初始所有值为0
    int j = 0;                       // 前缀指针，初始指向模式串第一个字符
    // i 从1开始，表示后缀的末尾
    for (int i = 1; i < m; i++) {
        // 当当前后缀字符不等于当前前缀字符时，前缀指针回退到之前匹配到的位置
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];         // 利用已计算的next值回退
        }
        // 如果相等，前缀指针前进
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;                 // 记录当前后缀的最长相同前后缀长度
    }
    return next;
}

// KMP搜索主函数：在文本text中查找模式pattern
void kmpSearch(const string& text, const string& pattern) {
    vector<int> next = getNext(pattern);   // 先构造next数组
    int n = text.size();                   // 文本长度
    int m = pattern.size();                // 模式长度
    int j = 0;                             // 模式串的当前指针
    // 遍历文本的每一个字符
    for (int i = 0; i < n; i++) {
        // 如果当前字符不匹配，并且模式指针>0，则利用next数组回退
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];               // 类似侦探发现线索，跳转到可能的位置
        }
        // 如果匹配，模式指针前进
        if (text[i] == pattern[j]) {
            j++;
        }
        // 如果模式指针走到了末尾，说明找到了一处完整匹配
        if (j == m) {
            cout << "找到匹配，起始位置: " << i - m + 1 << endl;
            j = next[j - 1];               // 继续寻找下一个匹配（模式串滑动）
        }
    }
}

int main() {
    // 例子1：普通场景
    string text1 = "ABCABCABC";
    string pattern1 = "ABCABC";
    cout << "在 \"" << text1 << "\" 中查找 \"" << pattern1 << "\"：" << endl;
    kmpSearch(text1, pattern1);

    cout << endl;

    // 例子2：贴合生活的场景——在句子中找单词
    string text2 = "我爱编程编程使我快乐";
    string pattern2 = "编程";
    cout << "在 \"" << text2 << "\" 中查找 \"" << pattern2 << "\"：" << endl;
    kmpSearch(text2, pattern2);

    cout << endl;

    // 例子3：模式串重复出现的场景
    string text3 = "ababaababab";
    string pattern3 = "abab";
    cout << "在 \"" << text3 << "\" 中查找 \"" << pattern3 << "\"：" << endl;
    kmpSearch(text3, pattern3);

    return 0;
}

运行结果：

在 "ABCABCABC" 中查找 "ABCABC"：
找到匹配，起始位置: 0
找到匹配，起始位置: 3

在 "我爱编程编程使我快乐" 中查找 "编程"：
找到匹配，起始位置: 2
找到匹配，起始位置: 5

在 "ababaababab" 中查找 "abab"：
找到匹配，起始位置: 0
找到匹配，起始位置: 2
找到匹配，起始位置: 6
找到匹配，起始位置: 8

常见错误与避坑指南

  1. next数组索引越界
    在回退代码中 j = next[j-1]，要确保 j>0，否则 j-1 为负数。所以 while 条件里一定要先判断 j>0。有些初学同学忘了加这个条件，运行时会数组越界崩溃。

  2. next数组的偏移理解混乱
    不同教程对next数组的定义有细微差别。有的定义 next[i] 表示当第 i 个字符匹配失败时，下一个要比较的字符索引（即可能等于 i 本身）。我们这里的定义是：next[i] 表示以 pattern[i] 结尾的子串的最长相同前后缀长度，匹配失败时用 next[j-1]。理解统一即可，不要混用。

  3. 匹配成功后的二次查找忘记重置 j
    找到匹配后，如果还想继续找后面的匹配，需要执行 j = next[m-1]（即模式串滑动）。如果忘记这步，j 会 remain 为 m，导致后续比较出错（因为 j 已经超出模式串长度）。

  4. 模式串为空的特殊情况
    如果模式串为空（长度为0），getNext 会返回空vector，然后 kmpSearch 中 j 永远为0，while 循环可能不会执行，但此时查找会输出什么？通常认为空串匹配任何文本，但实际代码需要处理。可以加一个if (m == 0) 直接返回。

  5. next数组与匹配时的下标对应
    在 getNext 里，我们计算的是“以i结尾的后缀的最长前缀长度”。在匹配时，如果 text[i] != pattern[j]，我们回退到的位置是 next[j-1]（即前面已匹配部分的最长前缀长度）。初学者容易搞混：为什么是 j-1 而不是 j？因为当前匹配失败的字符索引是 j，而已经匹配好的部分是 pattern[0..j-1]，所以回退的线索来自这 j 个字符。

更多指引

KMP算法是字符串匹配的经典算法，理解它之后，你还可以学习：

  • Boyer-Moore算法：另一种更快的字符串匹配算法，从右向左比较，常常比KMP更快，适合长文本搜索。
  • Z算法（Z函数）：也是O(n)的字符串算法，可以快速计算字符串的最长公共前后缀，常用于字符串匹配和模式查找。
  • Rabin-Karp算法：利用哈希进行匹配，适合多模式匹配问题（例如在一段文本里找多个单词）。
  • AC自动机（Aho-Corasick）：多模式匹配的终极武器，像KMP的升级版，一次扫描找出所有模式串在文本中的位置。

KMP的思想——利用已经计算好的信息避免重复计算——不仅适用于字符串，也广泛应用于其他算法（如状态机、动态规划中的“记忆化”）。掌握它，你就掌握了一种非常重要的优化思路。

例题精讲

1单选题

给定模式串"ABABAC"，按照KMP算法（next数组定义：next[0]=-1，next[i]表示模式串前i个字符的最长相同前后缀长度），其next数组为？

A[-1,0,1,2,3,0]
B[-1,0,0,1,2,3]
C[0,0,1,2,3,0]
D[-1,0,1,2,3,4]
2判断题

KMP字符串匹配算法的时间复杂度为O(n+m)，其中n为主串长度，m为模式串长度，且在最坏情况下仍为线性时间。

3填空题
以下为KMP算法中求next数组的代码片段，请补全空白处。

void getNext(string p, int next[]) {
    int m = p.length();
    next[0] = -1;
    int k = -1, j = 0;
    while (j < m - 1) {
        if (k == -1 || p[j] == p[k]) {
            ++j; ++k;
            next[j] = k;
        } else {
            k = ___;
        }
    }
}

填空处应填写什么？
4单选题

对于模式串"AAAA"，其优化后的nextval数组（即基于nextar的改进，当p[j]==p[next[j]]时令nextval[j]=nextval[next[j]]）是？

A[-1,0,1,2]
B[-1,-1,-1,-1]
C[0,0,0,0]
D[-1,0,0,0]
5判断题

在KMP匹配过程中，当主串字符与模式串字符不相等时，模式串指针j会跳转到next[j]的位置，而主串指针i保持不变。