首先我们看一个经典的字符串匹配问题:给定一个文本串 $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: 点击

---

字符串周期

对字符串 $S$ 和 $0 \le r < |S|$，若 $S$ 长度为 $S$ 的前缀和长度为 $S$ 的后缀相等，就称 $S$ 长度为 $r$ 的前缀是 $S$ 的 border．

根据前缀函数的定义，可以得到 $s$ 所有的 border 长度，即 $nxt[n-1],nxt[nxt[n-1]-1], \cdots．$

对字符串 $S$ 和 $0 < p \le |S|$，若 $S[i] = S[i+p]$ 对所有 $i \in [0, |S| - p - 1]$ 成立，则称 $p$ 是 $S$ 的周期．

由 $S$ 有长度为 $r$ 的 border 可以推导出 $|S|-r$ 是 $S$ 的周期．

所以根据前缀函数可以在 $O(n)$ 的时间内计算出 $S$ 所有的周期．其中，由于 $nxt[n-1]$ 是 $S$ 最长 border 的长度，所以 $n - nxt[n-1]$ 是 $S$ 的最小周期．

P4391 [BalticOI 2009]无线传输

求最小循环节长度

UVA1328 Period

【题意简化】 如果一个字符串 S 是由一个字符串 T 重复 K 次形成的，则称 T 是 S 的循环元。使 K 最大的字符串 T 称为 S 的最小循环元，此时的 K 称为最大的循环次数。

现在给定一个长度为 N 的字符串 S,对 S 的每一个前缀 S[1...i] ，如果它的最大循环次数大于 1，则输出该前缀的最小循环元长度和最大循环次数。

【分析】求每一个前缀的循环元，并且保证至少由两次构成。i-nxt[i-1] 就是循环元长度，如果是能整除 i ，那么至少由两次构成。

---

统计每个前缀的出现次数

CF432D Prefixes and Suffixes

---

其他经典例题

1. P4824 [USACO15FEB] Censoring S

栈+KMP

2. [NOI2014] 动物园

---

Z 函数（exKMP）

Z 函数（Z-algorithm，在国内也被称为扩展 KMP 算法），在信息学竞赛（OI/ACM）中，Z 函数的地位极其重要。它不仅能做到 KMP 能做的一切，而且其定义更直观、推导更优美，在处理很多复杂的字符串前后缀匹配问题时，比 KMP 好写、好想得多。

一、 什么是 Z 函数？

约定字符串下标从 $0$ 开始.

对于一个长度为 $n$ 的字符串 $S$，定义函数 $z[i]$ 表示 $S$ 和 $S[i,n-1]$（即以 $S[i]$ 开头的后缀）的最长公共前缀（LCP）的长度，则 $z$ 被称为 $S$ 的 Z 函数．特别地，$z[0] = 0$．

动手可以计算一下，$S = \text{"abacaba"}$, 那么 Z 函数就是 $Z=\{0,0,1,0,3,0,1\}$.

二、如何求 Z 函数

计算 z[i] 时利用前面已经计算出的信息，分类讨论解决。

for(int i=1,l=0,r=0;i<b.size();i++)
    {
        if(i<=r && z[i-l]<r-i+1)z[i]=z[i-l];
        else{
            z[i]=max(0,r-i+1);  //当 i>r 时 z[i]=0 暴力计算 ； 或 z[i-l]>=r-i+1 后续的也要暴力计算
            while( i+z[i]< b.size() && b[i+z[i]]==b[z[i]])++z[i];
            //将 r 更新为最右侧 r
            if(i+z[i]-1>r)l=i,r=i+z[i]-1;
        }
    }

P5410 【模板】扩展 KMP / exKMP（Z 函数）

【参考代码】 点击