！注意！本文与《王道》，《严书》有所不同，字符串均从第 0 位开始，next 数组没有添加常数 1。博客为梳理思路所用，难免纰漏，希望不吝赐教。
在字符串匹配中，设 m 为待匹配的主串 S 长度，n 为找寻的模式串 T 长度。
如：在主串 S = 'ababc' 中寻找模式串 T = 'abc' 则字符串匹配算法返回 S 中第一个匹配字串开始的位置下标 2，即 S 中的第二个 'a' 的位置.（原则上可以找到所有匹配字符串，方便起见只找寻第一个）
简单匹配算法（暴力求解）
介绍暴力求解算法是为了凸显 KMP 算法的强大。
不论何种算法，计算机均是一个字符一个字符地进行匹配。记 S 串中正在考察的字符的下标为 i,T 串为 j.（i,j 均从 0 开始）
简单匹配算法原理为，从模式串的第 0 个字符，到第 n - 1 个字符与主串匹配，遇到不匹配的情况则将模式串整体向右移动一位，可以看到，最坏的时间复杂度为 O(m*n)，如 T = '00001',S = '000000000000000000000000001'
如上图所示，简单匹配算法中第三趟已成功匹配 4 个字符，可以从已经匹配的 abca 得知（因为这时主串和模式串的前 4 个字符完全相等），将模式串向后移动 1 位的结果将是 a 与 b 比较，显然他们是不等的。故简单匹配算法中的一次移动一个字符的匹配方法，没有用上已经匹配过的信息。
KMP 算法
KMP 算法具有 O(m+n) 的时间复杂度。
引入
KMP 的核心思想为充分利用模式串本身的信息。模式串 T 的信息用 next[n] 的数组进行保存。
为了便于理解，我们引入以下概念：
- 前缀：除了字符串中最后一个字符 \(\alpha\) 外，其前面的所有字符所组成字符串的子串（子串需要包括第一个字符）之并。例如
ab其前缀为 {a}，对于abc，其前缀为 {a,ab} - 后缀，除了字符串中第一个字符 \(\beta\) 外，其后面所有字符所组成字符串的子串之并。（子串需要包括最后一个字符）例如
ab其后缀为 {b}，对于abc，其后缀为 {c,bc} - 最大部分匹配：对于一个字符串，其某个前缀与某个后缀相同，且没有更大的前缀或后缀满足此要求，该前缀（或后缀）为这个字符串的最大部分匹配。如
ab，的最大部分匹配字符串为 \(\empty\)，abcab为ab - PM 数组（partial match），用于辅助构造
next[n]数组，PM[i] 表示字符串 \(t_0t_1\space...\space t_i\) 的最大部分匹配字符串长度。
例 1
T: a b c a c
PM: 0 0 0 1 0
根据 PM 构造 next 数组
PM 数组是我觉得王道方法中最聪明的一点，搭建了到 next 数组的桥梁，同时也便于用观察法看出答案
假设最后一个成功匹配字符的下标为 j - 1，注意到，模式串 T 向右移动的位数应当为 已匹配位数 j - 最大部分匹配长度 (PM[ j - 1 ]) 即:
模式串 T 为 abcac ，如上图所示，最后一个匹配的字符为 T[1] = b，由上方 例 1 可知 PM[1] = 0，即子串 ab 的最大部分匹配长度为 0，则模式串 T 向后移动 2 - 0 = 2 位，如下图所示。（红色框为当前正在比较的字符串）
为什么可以这样计算呢？
- 由前情假设，主串和模式串已匹配的长度为 \(j\) 可知，\(s_{i-j}s_{i-j+1}\space...\space s_{i-1}\) = \(t_0t_1\space...\space t_{j-1}\)，现在将模式串向右移动，等价于用 \(t_0t_1\space...\space t_{j-1}\) 的某前缀字符串与其某后缀字符串匹配，同时也等价于用 \(s_{i-j}s_{i-j+1}\space...\space s_{i-1}\) 的某个前缀字符串匹配其某个后缀字符串。
- 由 PM 定义可知，假设 PM[ j ] = k，(k>0) 则有 \(t_0t_1\space...\space t_{k-1}\) = \(t_{j-k}t_{j-k+1}\space...\space t_{j-1}\)，且不存在 \(k^\prime\gt k\) 使得 \(t_0t_1\space...\space t_{k^\prime-1}\) = \(t_{j-k^\prime}t_{j-k^\prime+1}\space...\space t_{j-1}\)
- \(t_0t_1\space...\space t_{j-1}\) 的最大部分匹配字符串，意味着模式串需要右移的距离最小。任何右移长度小于 j - k 的操作意味着失配。如：
若主串 S 为
abcabp。模式串 T 为abcabd，其 PM 数组为 {0, 0, 0, 1, 2, 0}。在d字符处失配，有 j = 5, PM[ j - 1] = 2，最大部分匹配字符串为ab，则右移的最小距离为将abcabd中前缀的ab与后缀的ab对齐，即右移 \(j - PM[ j - 1] = 5 - 2 = 3\) 位。
如果向右移动距离过小，会导致失配，如下图：
通过 PM 得到 next
在字符串比较中，我们的改变比较字符的方式是移动指示当前比较字符的指针（即数组下标。主串 S 为 i，模式串 T 为 j）。next 数组就记录了模式串指针的变换，next[j] 表示第 j 位上的字符失配时，比较指针 j 将被赋值为 next[j] 继续与 S[i] 进行比较。next 数组将直观上模式串整体的右移，转换为模式串比较指针 j 的左移。数值计算方法：
对于 j 为 0 的情况，若第一个失配，则会移动主串 S 的比较指针，\(i = i + 1.\) 规定 \(next[0] = -1.\) （后续会看到置为 -1 的作用）
仍然回到这个例子：
T: a b c a c
PM: 0 0 0 1 0
next: -1 0 0 0 1
构造 next 数组算法
在刚才的方法中，PM 数组我们是通过观察得出的，对于计算机如何得到 next 数组呢？
上述公式的另一种表达方式如下：
采用一种递推的方式获取 next[j] 值，假设 next[j - 1] = k - 1 = ptr，即新建一个指针变量 ptr，请注意，k - 1 的值表示了 \(t_0t_1\space ... \space t_{j-2}\) 的最大部分匹配长度（设\(j\ge 2\)），下文中所做的字符对比均为 \(t_{ptr}\) 与 \(t_{j-1}\) 间的对比：
- 当 \(\bold{t_{ptr} = t_{j-1}}\) 时，有 \(t_0t_1\space ...\space t_{k-1} = t_{j-k}t_{j-k+1}\space ...\space t_{j-1}\)，则 \(t_0\space ...\space t_{j-1}\) 最大部分匹配长度为 k，即 $next[j] = ptr + 1\iff next[j] = next[j-1] + 1 $
举个例子：对模式串 T =
abcabd，求其 next[5]，即d所对应next值。由 \(t_{next[4]}=t_1=t_{j-1}=t_4=b\)，可知next[5] = next[4] + 1 = 2
- 当 \(\bold{t_{ptr} \ne t_{j-1}}\) 时，求取最长的 k 又可以视为一个字符串匹配问题。子模式串 T' = \(t_0t_1\space ...\space t_{k-1}\) 对 T 进行匹配，由于第 k - 1 位失配，故 \(ptr = next[ptr]\)，即等价于将子模式串 T' 向右移动。此时再次将 \(t_{ptr}\) 与 \(t_{j-1}\) 比对，若相等，则同第一种情形 \(next[j] = ptr+1\)；若不等，则重复进行 \(ptr=next[ptr]\) 的赋值。当 \(ptr\) 被赋值为 -1 时，表示 \(PM[j-1] = 0\)，故 \(next[j] = 0\)，也满足 \(next[j] = ptr + 1.\)
举个例子：对模式串 T =
abcabde，求其 next[6]，即e所对应next值。由 \(t_{ptr} = t_{next[5]}=t_2=c\ne t_{j-1} = t_5 = d\)，故失配，用新的子模式串 T' =abc（\(t_0t_1\space ...\space t_{k-1}\)）来匹配 T，子模式串指针ptr移动到next[ptr]上，得到ptr = 0。
子模式串移动后：
仍然失配，但是当前的next[ptr] = -1，无法再移动，即 \(t_0t_1\space...\space t_5\) 的最长部分匹配长度为 0，故赋值next[j] = 0，即next[6] = 0.
next 数组构造 C 语言表示
// 辅助数据结构
typedef struct {
char *str; // 字符串
int length; // 字符串长度
} String;
// 根据上方分析我们得到：
// 1. 当 ptr = -1 或 T[ptr] = T[j-1] 时，有 next[j] = ptr + 1.
// 2. 当 ptr != -1 且 T[ptr] != T[j-1] 时，有 ptr = next[ptr]
void calculateNext(String T, int next[]){
int n = T.length;
// 注意到对模式串 T 现在作为字符串匹配的主串，其指针不会回退，只会前进。利用此特点从 0 ~ n-1 计算 next 数组
int j = 1, ptr;
next[0] = -1; // 将第一个字符对应的 next 置为 -1
ptr = next[0]; // 一开始计算 next[1] 时，ptr = next[1-1] = next[0]
while (j < n) {
if (ptr == -1 || T.str[ptr] == T.str[j - 1]) {
// 满足 1.
next[j] = ptr + 1;
j++;
ptr++;
}
else {
// 满足 2.
ptr = next[ptr];
}
}
}
KMP 匹配算法
现在有了 next 数组，再来进行匹配就十分方便了。
// 1. 当 j != -1 且 S[i] = T[j] 时，i++,j++，（成功匹配两串均移动一位）
// 2. 当 j != -1 且 S[i] != T[j] 时，即失配。j = next[j].等价于模式串右移。
// 3. 当 j = -1 时，表示 S[i] 与 T[0] 不匹配，需要移动主串，同时模式串的比较指针也需要移动到第 0 位 i++,j++;（与第一种情形统一起来）
// S：主串
// T：模式串
// next: 模式串的 next 数组
// return：返回主串中第一个匹配到的子串的首字符下标，没有匹配子串则返回 -1
int KMP(String S, String T, int next[]) {
// 与构造 next 数组同，主串指针只增不减。
int i = 0,j = 0;
int matchPtr = -1; // 返回的数组下标
while (i < S.length && j < T.length) {
if (j == -1 || S.str[i] == T.str[j]) {
// 情形 1. 3.
j++;
i++;
}
else {
// 情形 2.
j = next[j];
}
}
if (j == T.length) {
// 表明找到匹配串
matchPtr = i - T.length;
}
return matchPtr;
}
小总结
再次重申，KMP 算法核心思想为：利用主串和模式串中已经匹配了的字符串的信息，这就做到了主串不回溯（主串的匹配指针只能增加）。如何利用已匹配信息呢：在模式串 T 的 T[ j ] 失配，隐含着 T[ 0 ]~T[ j - 1 ] 均匹配，则只用考虑模式串本身的结构即可——计算 next 数组。
计算 next 数组的两种方法：
- 通过部分匹配数组（PM）计算，由于观察法可以轻松看出匹配的最长前缀和后缀，除了
next[0] = -1外其余next值只用把 PM 数组的值向右平移一位即可。（方便记忆，加速计算） - 通过 \(next[j] = ptr + 1\) 和 \(ptr = next[ptr]\) 公式递推得到
next数组，注意j的开始值取 1，ptr值取 -1，(因为next[0]\(\equiv\)-1，next[1]\(\equiv\) 0) 这主要用于算法实现。
KMP 算法本身就是根据 next 数组移动模式串的比较指针的过程，这在用公式法计算 next 数组时已经有所体现。
注：《严书》和《王道》中采用将 next 数组整体加 1 的格式，主要由于其字符串下标从 1 开始。
进一步优化
KMP 算法还有优化的空间，即利用 T[ j ] 失配的信息，见下例：
主串 S 为 aaabaaaab,模式串 T 为 aaaab，计算得到 T 的 next 数组如下图，当 S[3] 与 T[3] 失配时，S[3] 还需要与 T[2]，T[1]，T[0] 进行三次注定失配的比较，因为 T[0] = T[1] = T[2] = T[3].也就是将模式串右移后 j 指向的字符与右移前相同。这个相等的信息，在 next 数组中可以包含进去。即 若 \(t_{next[j]} = t_{j}\)，则 \(next[j] = next[ptr]\) ，注意这里的 \(ptr\) 是指已经 +1 后的，也可以理解为 \(next[j] = next[next[j]]\)。
// 改进的 next 数组计算
void calculateNextVal(String T, int nextVal[]){
int n = T.length;
// 注意到对模式串 T 现在作为字符串匹配的主串，其指针不会回退，只会前进。利用此特点从 0 ~ n-1 计算 nextVal 数组
int j = 1, ptr;
nextVal[0] = -1; // 将第一个字符对应的 nextVal 置为 -1
ptr = nextVal[0]; // 一开始计算 nextVal[1] 时，ptr = nextVal[1-1] = nextVal[0]
while (j < n) {
if (ptr == -1 || T.str[ptr] == T.str[j - 1]) {
// 满足 1.
nextVal[j] = ptr + 1;
ptr++;
// 将第 j 位失配的信息传递到 next 数组，也就是需要额外判断更新之后的 next[j](即当前 ptr) 是否与 j（失配位）所指向字符相同
if (T.str[nextVal[j]] == T.str[j]) {
// str[next[j]] 与 str[j] 相同，重新设置 next[j] 的值
nextVal[j] = nextVal[ptr];
}
j++;
}
else {
// 满足 2.
ptr = nextVal[ptr];
}
}
}
参考文献
- 2022 数据结构与算法《王道》学习笔记（十一）KMP 算法 详细归纳总结 改进的模式匹配算法
- 2025《王道数据结构》
- 《数据结构（C 语言版）》严蔚敏 吴伟民