1 简介
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。 [1] ^{\texttt{[1]}} [1]
KMP算法的时间复杂度为 O ( n + m ) O(n+m) O(n+m) 。
原有的传统暴力字符串匹配算法中，当匹配模式串和主串出现错误时，需要退回起始位置，而KMP算法的效率在于，当匹配模式串失败后不会退回，而会根据错误信息继续向后匹配。
| KMP算法的提出者之一——唐纳德·克努特（Donald Ervin Knuth） [2] ^{\texttt{[2]}} [2] ，是1974年图灵奖获得者，也是计算机排版系统 TeX \TeX TEX [3] ^{\texttt{[3]}} [3]的发明者。他的著作《计算机程序设计的艺术》，被评为可以与《几何原本》《相对论》相提并论。 |  |
|---|
2 KMP算法
2.1 Next
border（边界）： 指字符串的最长公共前后缀。border的长度必须严格小于原字符串的长度。
例如，字符串 abcdab 的border为 ab。
N e x t i Next_i Nexti ： 指以第 i i i 个字符结尾的前缀（严格前缀）的border的长度。 N e x t Next Next 只针对模式串。
为了方便编程，令字符串和 N e x t Next Next 的下标均从 1 1 1 开始，并把 N e x t i Next_i Nexti 定义为：字符串下标从 1 ∼ i 1\sim i 1∼i 的子串的border的长度。（易知 N e x t 1 = 0 Next_1=0 Next1=0）
| 下标 i i i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 举例字符串 s s s | a | b | a | b | c | d | a | c | a | b |
| border | - | - | a | ab | - | - | a | - | a | ab |
| N e x t Next Next | 0 | 0 | 1 | 2 | 0 | 0 | 1 | 0 | 1 | 2 |
可以发现：
如果 s i = s N e x t i − 1 + 1 s_i=s_{Next_{i-1}+1} si=sNexti−1+1（如下图所示，红色部分为上一个子串的border的位置，蓝色部分分别是 s N e x t i − 1 + 1 s_{Next_{i-1}+1} sNexti−1+1 和 s i s_i si），则 N e x t i = N e x t i − 1 + 1 Next_i=Next_{i-1}+1 Nexti=Nexti−1+1；
如果 s i = s N e x t N e x t i − 1 + 1 s_i = s_{Next_{Next_{i-1}}+1} si=sNextNexti−1+1，同理， N e x t i = N e x t N e x t i − 1 + 1 Next_i=Next_{Next_{i-1}}+1 Nexti=NextNexti−1+1；
如果 s i = s N e x t N e x t N e x t i − 1 + 1 s_i = s_{Next_{Next_{Next_{i-1}}}+1} si=sNextNextNexti−1+1，同理， N e x t i = N e x t N e x t N e x t i − 1 + 1 Next_i=Next_{Next_{Next_{i-1}}}+1 Nexti=NextNextNexti−1+1；
… … \dots\dots ……
令 j = N e x t i − 1 j=Next_{i-1} j=Nexti−1，不断向前询问是否满足 s i = s j + 1 s_i=s_{j+1} si=sj+1，满足，则 N e x t i = j + 1 Next_i=j+1 Nexti=j+1；反之， j = N e x t j j=Next_j j=Nextj 继续询问，直到 j = 0 j=0 j=0 为止。
代码如下（Next[]和s均从下标为 1 1 1 开始）：
void get_next(string s) {
int i, j;
for (Next[1] = j = 0, i = 2; s[i]; i++) {
while (j && s[i] != s[j + 1])
j = Next[j];
if (s[i] == s[j + 1])
j++;
Next[i] = j;
}
}
2.2 模式匹配
KMP算法的模式匹配思路是：对于匹配失败的模式串，把位置向后移动，使**模式串匹配部分的前缀border位置与后缀border位置原来所对应的主串位置相对应。**如果无法移动，向右移动 1 1 1 位。
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 说明 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 举例主串 s s s | a | b | a | c | a | a | b | a | a | b | a | b | - |
| 举例模式串 p p p | a | b | a | b | - | ||||||||
| N e x t Next Next | 0 | 0 | 1 | 2 | - | ||||||||
| 操作1 | √ \color{green}{√} √ | √ \color{green}{√} √ | √ \color{green}{√} √ | × \color{red}{×} × | 匹配错误 | ||||||||
| a | b | a | b | border对齐 | |||||||||
| 操作2 | √ \color{green}{√} √ | × \color{red}{×} × | 匹配错误 | ||||||||||
| a | b | a | b | 右移 1 1 1 位 | |||||||||
| 操作3 | × \color{red}{×} × | 匹配错误 | |||||||||||
| a | b | a | b | 右移 1 1 1 位 | |||||||||
| 操作4 | √ \color{green}{√} √ | × \color{red}{×} × | 匹配错误 | ||||||||||
| a | b | a | b | 右移 1 1 1 位 | |||||||||
| 操作5 | √ \color{green}{√} √ | √ \color{green}{√} √ | √ \color{green}{√} √ | × \color{red}{×} × | 匹配错误 | ||||||||
| a | b | a | b | border对齐 | |||||||||
| 操作6 | √ \color{green}{√} √ | × \color{red}{×} × | 匹配错误 | ||||||||||
| a | b | a | b | 右移 1 1 1 位 | |||||||||
| 操作7 | √ \color{green}{√} √ | √ \color{green}{√} √ | √ \color{green}{√} √ | √ \color{green}{√} √ | 匹配成功 |
注：标黄部分表示匹配的部分的border。
可以发现：
如果 s i = p N e x t i − 1 + 1 s_i=p_{Next_{i-1}+1} si=pNexti−1+1（也就是说， p p p 的前一个border的下 1 1 1 位与 s i s_i si 相匹配，此时就匹配成功了一次），模式串移动到 N e x t i − 1 + 1 Next_{i-1}+1 Nexti−1+1；
如果 s i = p N e x t N e x t i − 1 + 1 s_i=p_{Next_{Next_{i-1}}+1} si=pNextNexti−1+1，模式串移动到 N e x t N e x t i − 1 + 1 Next_{Next_{i-1}}+1 NextNexti−1+1；
如果 s i = p N e x t N e x t N e x t i − 1 + 1 s_i=p_{Next_{Next_{Next_{i-1}}}+1} si=pNextNextNexti−1+1，模式串移动到 N e x t N e x t N e x t i − 1 + 1 Next_{Next_{Next_{i-1}}}+1 NextNextNexti−1+1；
… … \dots\dots ……
令 j = N e x t i − 1 j=Next_{i-1} j=Nexti−1，不断向前询问是否满足 s i = p j + 1 s_i=p_{j+1} si=pj+1，满足，则 j = j + 1 j=j+1 j=j+1；反之， j = N e x t j j=Next_j j=Nextj 继续询问，直到 j = 0 j=0 j=0 为止。
代码如下（Next[]，p和s均从下标为 1 1 1 开始）：
void KMP(string s, string p) {
int i, j;
for (i = 1, j = 0; s[i]; i++) {
while (j && s[i] != p[j + 1])
j = Next[j];
if (s[i] == p[j + 1])
j++;
if (!p[j + 1])
j = Next[j];
}
}
3 例题
3.1 剪布条
题目描述
对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条。
题解
简单明了，模板即可。但注意，不应出现模式串两处匹配后重叠的情况。
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
int n, Next[N], ans = 0;
string s, p;
void get_next(string s) { /*some code...*/ }
void KMP(string s, string p) {
int i, j, prev = 0;
for (i = 1, j = 0; s[i]; i++) {
while (j && s[i] != p[j + 1])
j = Next[j];
if (s[i] == p[j + 1])
j++;
if (!p[j + 1]) {
j = Next[j];
if (prev + p.size() - 1 <= i) {
//避免重叠 prev记录前一次匹配的右端点位置
prev = i;
ans++;
}
}
}
}
int main() {
CLOSE;
while (cin >> s >> p && s != "#") {
s = " " + s;
p = " " + p;
ans = 0;
get_next(p);
KMP(s, p);
cout << ans << endl;
}
return 0;
}
3.2 字符串最大值
题目描述
给出一个长度为 n n n 的字符串，求出所有前缀的出现的次数×长度的最大值。
题解
不妨这样假设：
长度为 i i i 的前缀出现了 c n t i cnt_i cnti 次，而每次出现的前缀里都有 2 2 2 个长度为 N e x t i Next_i Nexti 的border，每个额外拥有一个长度为 N e x t i Next_i Nexti 的前缀，则 c n t N e x t i cnt_{Next_{i}} cntNexti 应当累加进去 c n t i cnt_i cnti。从后往前求出 c n t cnt cnt 表即可。
//some code...
get_next(s);
for (int i = s.size() - 1; i >= 1; i--) {
cnt[i]++;
cnt[Next[i]] += cnt[i];
ans = max(ans, cnt[i] * i);
}
//some code...
