首先我们看一个经典的字符串匹配问题:给定一个文本串 $S$（长度为 $N$）和一个模式串 $P$（长度为 $M$），求 $P$ 在 $S$ 中出现的所有位置。

暴力（Brute Force）做法：

用两个指针 i 和 j 分别指向 S 和 P。如果当前字符匹配成功，i++, j++；如果失配（不相等），i 回溯到本次匹配起点的下一位，j 清零重来。时间复杂度 $O(NM)$

一、暴力算法缺陷:

假设 S = "aaaaaabaaaaaa"，P = "aaaaaab"。当匹配到 P 的最后一个字符 'b' 时失败了，暴力算法会把 i 移回 S 的第二个字符，j 移回 P 的开头，重新开始数 a。

核心痛点： 之前的匹配过程已经提供了大量信息（我们明明知道前面很长一段全是匹配的），但暴力算法把这些信息全部扔掉了，导致了大量的重复计算。时间复杂度直接飙升到 $O(N \times M)$。

二、 KMP 的核心：i 绝不回头，让 j 去跳跃

举个例子： 假设我们在 P 的 j 位置失配了，而 P[0...j-1] 是已经匹配成功的部分："ABACABA"。

它的前缀有："A", "AB", "ABA", "ABAC"...

它的后缀有："A", "BA", "ABA", "CABA"...

其中相同且最长的是："ABA"（长度为 3）。

既然这段 "ABA" 既是前缀又是后缀，而后缀刚刚已经和主串 S 匹配上了，那就意味着前缀也一定能和主串对得上！ 我们不需要把 j 归零，直接把 j 跳到索引 3（也就是下一个等待匹配的字符），继续和 i 比较即可。

那么也就是为了方便 j 的跳转，我们需要想办法维护出模式串 P 的相等的后缀与前缀，并且这个长度尽量长，不能是本身，也就是最长的相等真前缀与真后缀，这就是前缀函数。

三、核心:前缀函数

为了让 j 知道跳到哪里，我们需要预处理模式串 P 的前缀函数，很多教程里面称为 nxt[] 或 pi[] 。

前缀函数 nxt[i] 的定义：模式串 P[0...i] 这一段子串中，最长相等真前缀与真后缀的长度（不能等于子串自身）。

字符串的前缀和后缀的相同部分叫做 border ，那么前缀函数就是最长的 border.

计算 nxt[i] 的过程，要充分利用前面已经知道的信息，我们已经计算知道 nxt[i-1] , 这个长度记为 j , 那么示意图如下:

$$\overbrace{\underbrace{P_0P_1\cdots P_{j-1}}_j}^{nxt[i-1]} P_j\cdots \overbrace{\underbrace{P_{i-j} \cdots P_{i-1}}_j}^{nxt[i-1]}P_i$$

当 $P_i \ne P_j$ 时，那么 $j$ 就要往前跳，等价位置就是 $j=nxt[j-1]$.

vector<int> getNxt(string P) {
    int M = P.length();
    vector<int> nxt(M, 0);
    int j = 0; // j 表示最长相等前后缀的长度，同时也指向前缀的下一个待匹配字符
    
    for (int i = 1; i < M; i++) {
        // 当字符不匹配时，j 顺着 next 数组往回跳（大智慧所在）
        while (j > 0 && P[i] != P[j]) {
            j = nxt[j - 1];
        }
        // 如果匹配成功，最长相等前后缀长度加 1
        if (P[i] == P[j]) {
            j++;
        }
        nxt[i] = j;
    }
    return nxt;
}

KMP 匹配过程

给定一个文本串 $S$（长度为 $N$）和一个模式串 $P$（长度为 $M$），求 $P$ 在 $S$ 中出现的所有位置。

两种解决思路：

1. P+"#"+S : + 是连接作用，然后直接求 nxt[] ，如果 nxt[i]=lenP ,说明 S 中找到 P.
2. 预处理计算 P 的 nxt[] 数组，然后进行匹配。参考如下:

void KMP(string S, string P) {
    int N = S.length();
    int M = P.length();
    vector<int> nxt = getNxt(P);
    
    int j = 0; // P 串的指针
    for (int i = 0; i < N; i++) { // i 是一路向前的
        while (j > 0 && S[i] != P[j]) {
            j = nxt[j - 1]; // 失配了，j 回跳
        }
        if (S[i] == P[j]) {
            j++; // 匹配成功，j 前进
        }
        
        // 成功找到一个完整匹配
        if (j == M) {
            cout << "Pattern found at index " << i - M + 1 << endl;
            j = nxt[j - 1]; // 让 j 顺着 next 往回跳，继续找下一个可能的匹配
        }
    }
}

例1. P3375 【模板】KMP

思路1: 点击

思路2: 点击