文章目录
一、前言
二、KMP 算法
1. 问题背景
2. 暴力匹配
2.1 暴力匹配过程
2.2 暴力匹配实现
3. KMP 算法
3.1 优化思路
3.2 k 值
3.3 KMP 算法实现过程
三、KMP 算法例题—— KMP 字符串
具体实现
1. 模板
1.1 代码注解
1.2 实现代码
2. 下标从0开始的写法（不建议）
2.1 实现代码
一、前言
KMP 算法是由 D.E.Knuth ，J.H.Morris 和 V.R.Pratt 三位学者在 Brute-Force 算法的基础上提出的模式匹配改进算法，因此人们称它为克努特—莫里斯—普拉特操作（简称 KMP 算法）。KMP 算法的核心是利用匹配失败后的信息，尽量减少主串与字符串串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next() 函数实现，函数本身包含了模式串的局部匹配信息。KMP 算法的时间复杂度 O(m+n) 。
Brute- Force 算法在模式串中有多个字符和主串中的若干个连续字符比较都相等，但最后一个字符比较不相等时，主串的比较位置需要回退。KMP 算法在上述情况下，主串位置不需要回溯，从而可以大大提高效率。
二、KMP 算法
1. 问题背景
如果我们有两个字符串，一个是长字符串 S ，另一个是短字符串 P ，这两个字符串中都只包含大小写英文字符和阿拉伯数字，现在我们要查找 P 在 S 中的位置，如果短字符串 P 在长字符串 S 中出现过，输出第一次出现的位置，否则输出 -1。
例如：长字符串 S = “ababababfab” ，短字符串 P = “ababf”，可以看出 P 在 S 中第一次出现位置是在S[4] 到S[8]，所以输出4。
例如：长字符串 S = “abababfab” ，短字符串 P = “ababg”，可以看出 P 在 S 中没有出现过，输出 -1。
2. 暴力匹配
2.1 暴力匹配过程
- 关于暴力匹配做法，我们依次比较长字符串各个字母为开头的字串是否与短字符串匹配。
- 依次比较以长字符串各个字母为开头的子串是否与短字符串匹配。
- 如果有匹配的输出起始位置，如果没有，输出 -1。
- 例如：以长的字符串 S = “ababababfab” ，短的字符串 P = “ababf” 为例，过程如下：
- 首先用S[0]开头的子串：ababa 与 P比较，不匹配。
- 接着用S[1]开头的子串：babab 与 P比较，不匹配。
- 接着用S[2]开头的子串：ababa 与 P比较，不匹配。
- 接着用S[3]开头的子串：babab 与 P比较，不匹配。
- 接着用S[4]开头的子串：ababf 与 P比较，匹配。输出4。
2.2 暴力匹配实现
首先我们假设，长字符串 S 匹配到 i 位置，短字符串 P 匹配到 j 位置。
如果当前字符串匹配成功（即 S[i] = P[j] ），则 i++ ， j++ ，继续匹配下一个字符。
如果当前字符串匹配失败（即 S[i] != P[j] ），则令 i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。因为 长字符串 S 当中 i - (j - 1) 位置之前的都与短字符串 P 进行对比过了，因此我们只需从该位置继续与短字符串 P 匹配即可。
int ViolentMatch(char* s, char* p) { int sLen = strlen(s); int pLen = strlen(p); int i = 0; int j = 0; while (i < sLen && j < pLen) { if (s[i] == p[j]) { i++; j++; } else { i = i - j + 1; j = 0; } } if (j == pLen) { return i - j; } else { return -1; } }
3. KMP 算法
- 暴力匹配做法的优缺点都很明显，容易被我们想到，但时间复杂度较高。
- 因此，KMP 算法就是用来优化暴力算法，降低时间复杂度。
3.1 优化思路
- 此处，仍以长字符串 S = “ababababfab” ，短字符串 P = “ababf” 为例。
- 首先，用 S[0] 开头的字串：“ababa” 与 P = “ababf” 比较，比较到 S[4] 与 P[4] 的时候，S[4] != P[4]。
- 如果按照暴力匹配的思路，此时应该使用 S[1] 开头的字串 “babab” 与 P = "ababf“ 进行匹配。
- 这时，我们会发现，S[1~3] 与P[0~2] 不匹配，因此，以 S[1] 开头的字符串一定与 P 不匹配，便不需要进行以 S[1] 为开头字符串与 P 的比较了。
继续比较，我们又会发现，S[2~3] 与 P[0~1] 匹配，则以 S[2] 为开头的字符串在与 P = "ababf“ 进行匹配时，可以直接从 S[4] 与 P[2] 开始比较即可。比较到S[6] 与 P[4] 的时候，S[6] != P[4]。
继续比较，我们又会发现，S[3~5] 与 P[0~2] 不匹配，则以 S[3] 为开头的字符串在与 P = "ababf“ 一定匹配失败时，便不需要进行以 S[3] 为开头字符串与 P 的比较了
-接下来用 S[4] 开头的子串： S[4] = “ababf“ 与 P = “ababf“ 比较。此时，由于 S[4~5] 与 P[0~2] 相同，那以S[4] 为开头的字符串与 P 匹配时，无需从S[4]开始，直接从S[5] 与 P[3] 开始比较即可。比较到S[8] 与 P[5] 的时候，S[8] = P[5]，字符串匹配完成，返回起始位置4。
总结一下，当出现了 S[i] != P[j] 时，我们进行检查： S[i-j+1 ~ i-1] 与 P[0 ~ j-2] 是否匹配，S[i-j+2 ~ i-1] 与 P[0 ~ j-3] 是否匹配······。也就是下图中 S 蓝色框里的子串与 P 蓝色框里的子串是否匹配，S 绿色框里的子串与 P 绿色框里的子串是否匹配，S 红色框里的子串与 P红色框里的子串是否匹配。
3.2 k 值
对上述实现过程进行总结，我们发现，只需要一个值 k ，k 是可以满足下面性质的最大值：
长字符串从 i-k 到第 i-1 的字符 S[i-k ~ i-1] 与短字符串前 k 个字符 P[0 ~ k-1] 相同。
对于大于 0 的 x:
（1） 长字符串从 i-k-x 到第 i-1 的字符 S[i-k-x ~ i-1] 与短字符串前 k-x 个字符 P[0 ~ k+x-1] 不相同。
（2） 长字符串从 i-k+x 到第 i-1 的字符 S[i-k+x ~ i-1] 与短字符串前 k-x 个字符 P[0 ~ k-x-1] 相同。
因为 k 是满足 P[0 ~ k-1] 与 S[i-k ~ i-1] 相同的最大值，所以 P[0 ~ k-1+x] 与 S[i-k-x ~ i-1] (x>0) 不同，因此以 S[i-k-x] 为开头的子串与 P 肯定不匹配。下次匹配，i 无需回溯到 i-k-x， 只需回溯到 i-k，j 回溯到 0。
因为 P[0 ~ k-1] 与 S[i-k ~ i-1] 相同，因此这一段无需比较。故 i 直接可以移动到回溯之前的位置，j 直接可以移动到 k 。
总结来看：当遇到不匹配的字符的时候，i 不往前移动，j 移动到 k 即可。
3.3 KMP 算法实现过程
此处，我们仍以长字符串 S = “ababababfab” ，短字符串 P = “ababf” 为例：
第一次出现字符不匹配的时候为：S[4] != P[4]。保证 P[0 ~ k-1] = S[4-k ~ 3] 的 k 的最大值为 2。
当 k = 4 时，匹配没有任何意义，k = 3 时，S[1] = b，与 P[0] 不相同，当 k = 2 时满足条件。
因为，k 的最大值为 2 ，S[1] 为开头的字符串，x = 1，所以 P[0 ~ 2+1-1] != S[2-1 ~ 3]， 即 P[0 ~ 2] != S[1 ~ 3]。因此以 S[1] 为开头的子串与 P 肯定不相同，无需进行后续比较。
接下来判断以 S[2] 为开头的字符串与 P 是否相同。又因为 P[0 ~ 1] = S[2 ~3]，所以转化为以 S[2] 为开头的字符串是否与 P 相同，只需要从 P[2] 与 S[4] 开始比较即可。i 之前的位置为 4，现在还是 4，相当于 i 没有回溯。j 之前的位置是 4 ，现在是 2 也就是 k 值，也没有回溯到 0。
KMP 中的最长公共前后缀长度数组：next 。next[j] 含义是：P[j] 前面的字符串的最长公共前后缀长度。使得字符串有最长相等前后缀的前缀的最后一位的下标。
仍以长字符串 S = “ababababfab” ，短字符串 P = “ababf” 为例，P=“ababf” 的最长公共前后缀：
P[0] 前面没有字符串，所以最长公共前后缀长度为 0。
P[1] 前面的字符串为：a，a 没有前后缀 (前后缀长度要小于字符串长度) 。最长公共前后缀长度为 0。
P[2] 前面的字符串为：ab，它的前缀为：a，后缀为b。前缀不等于后缀，所以没有公共前后缀，最长公共前后缀长度为 0。
P[3] 前面的字符串为：aba，aba 的前缀有：a，ab， 后缀有：a，ba。因为 ab 不等于 ba，所以最长公共前后缀为 a，最长公共前后缀长度为 1。
P[4] 前面的字符串为：abab，abab 的前缀有：a，ab，aba，后缀有：a，ab, bab。最长公共前后缀为 ab，长度为 2。
求 next 数组的过程：
初始化 next 数组，令 j = 0，i = 2，因为 next(1) = 0。
让 i 在 2 ~ len 范围内遍历，对每个 i ，执行 3、4，以求解 ne[i]。
直到 j 回退为 0，或是 p[i] = p[j + 1] 成立，否则不断令 j = ne[j]。
如果 p[i] = p[j + 1]，则 j = j + 1，之后，再将 j 赋值给 ne[i] 。
for (int i = 2, j = 0; i <= n; i ++ ) { while (j && p[i] != p[j + 1]) { j = ne[j]; } if (p[i] == p[j + 1]) { j ++ ; } ne[i] = j; }
- 通过 next 数组有了最长公共前后缀，因此当我们前缀部分匹配失败后，可以直接从后缀开始下一步匹配过程，形成跳跃式匹配的高效模式。
- KMP 算法的具体实现过程及代码可见例题。
三、KMP 算法例题—— KMP 字符串
题目描述
给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出模式串 P 在字符串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N，表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S 的长度。
第四行输入字符串 S。
输出格式
共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。
数据范围
1 ≤ N ≤ 1e5
1 ≤ M ≤ 1e6
输入样例
3
aba
5
ababa
输出样例
0 2
具体实现
1. 模板
1.1 代码注解
- 在 C++ 当中，next 数组在某个头文件当中已经被使用过了，因此直接使用 next 数组时有可能会报错。
- j = ne[j]。 下次匹配的时候，直接移动到相同后缀部分。
1.2 实现代码
#include <bits/stdc++.h> using namespace std; const int N = 100010, M = 1000010; int n, m; int ne[N]; char s[M], p[N]; int main() { cin >> n >> p + 1 >> m >> s + 1; // 求ne过程 for (int i = 2, j = 0; i <= n; i ++ ) { while (j && p[i] != p[j + 1]) { j = ne[j]; } if (p[i] == p[j + 1]) { j ++ ; } ne[i] = j; } // kmp匹配过程 for (int i = 1, j = 0; i <= m; i ++ ) { while(j && s[i]!= p[j+1]) //如果不匹配 j表示退无可退了 { j = ne[j]; //表示j退几步 } if(s[i] == p[j+1]) //如果他俩已经匹配了 { j++; //就可以移动到下一个位置 } if(j == n) //匹配成功 { cout << i-n << ' '; //i-n+1是下标, 但是题意从0开始, 所以还有减去1 j = ne[j]; } } system("pause"); return 0; }
2. 下标从0开始的写法（不建议）
2.1 实现代码
#include <bits/stdc++.h> using namespace std; const int N = 1000010; int n, m; char s[N], p[N]; int ne[N]; int main() { cin >> m >> p >> n >> s; ne[0] = -1; for (int i = 1, j = -1; i < m; i ++ ) { while (j >= 0 && p[j + 1] != p[i]) { j = ne[j]; } if (p[j + 1] == p[i]) { j ++ ; } ne[i] = j; } for (int i = 0, j = -1; i < n; i ++ ) { while (j != -1 && s[i] != p[j + 1]) { j = ne[j]; } if (s[i] == p[j + 1]) { j ++ ; } if (j == m - 1) { cout << i - j << ' '; j = ne[j]; } } system("pause"); return 0; }
