【算法详解】理解KMP，真的那么难吗？—— 一篇讲透它的核心思想
🫧 励志不掉头发的内向程序员：个人主页
✨️ 个人专栏: 《C++语言》《Linux学习》
🌅偶尔悲伤，偶尔被幸福所完善
👓️博主简介:
文章目录
前言
本文用尽量详细的语言来讲解说明 kmp 算法内容，学习之前需要知道一点点动态规划的基础，如果不知道最好去了解了解。我们一起来看看算法吧。
一、相关概念
在学习 kmp 算法之前，我们得先提前了解最基本的 “ 动态规划 ” 的知识，否则可能学习的时候会有一些困难，因为它的原理类似于动态规划。
字符串：
- 用字符构成的的序列就是字符串。
这个概念很简单，但是我们这里有个小技巧：就和动态规划那样，在字符串匹配问题中，我们会让字符串的下标从 1 开始，这样便于我们处理一些边界问题。因此，在输入字符串时，我们一般会在前面加上一个空格，这样字符串就会从 1 开始计数了。
string s; cin >> s;int n = s.size(); s =' '+ s;子串：
- 选取字符串中连续的一段。
例如：
字符串： abcdefg；
子串：cdefg、cde、abcdefg、a、b 等等；
前缀：
- 从字符串首端开始，到某一个位置结束的子串。
字符串长度为 i 的前缀，就是字符串 [ 1, i ] 区间的子串。
例如：
字符串：abcdefg；
长度为 3 的前缀为：abc；
长度为 5 的前缀为：abcde；
长度为 7 的前缀为：abcdefg（字符串本身）
注意：
这里默认字符串前面有一个空格，所以下标从 1 开始而非 0。
真前缀：
- 不包含字符串本身的前缀。
后缀：
- 从字符串某一个位置开始，到字符串末端的结束的子串。
字符串长度为 i 的后缀，就是字符串 [ n − i + 1, n ] 区间的子串。
例如：
字符串：abcdefg；
长度为 3 的后缀为：efg；
长度为 5 的后缀为：cdefg；
长度为 7 的后缀为：abcdefg（字符串本身）
真后缀：
- 不包含字符串本身的后缀。
真公共前后缀 / border 以及最长真公共前后缀的长度 / π：
- 字符串的真公共前后缀为⼀个子串 ，满足既是真前缀，又是真后缀，也称为字符串的 border。
- 在一个字符串中，最长的真公共前后缀的长度用 π 表示。
例如：
字符串：aabaaba；
真前缀：a、aa、aab、aaba、aabaa、aabaab、aabaaba；
真后缀：a、ba、aba、aaba、baaba、abaaba、aabaaba；
从上面我们可以发现，真前缀和真后缀相同的有 a、aaba。最长真公共前后缀的长度为 4。所以上述字符串的 π 值为 4 。
- 性质：
传递性：字符串 s 的 border 的 border 也是字符串 s 的 border。
字符串匹配：
- 字符串匹配又称模式匹配。给定两个字符串 S 和 T ，需要在主串 S 中找到模式串 T 。
例如：
主串 S = “abcdefcde”
模式串 T = “cde”
如果下标从 1 开始计数，模式串会在主串 3、7 位置出现。
关于字符串匹配，大家肯定能想到暴力解法，那就是拿着模式串，在主串中一个位置一个位置判断。但是，暴力解法极限情况，时间开销会达到 O(n × m)。而接下来要学习的 kmp，能在 O(n + m) 的线性时间内，找到所有的匹配位置，以及维护出更多的信息。
二、前缀函数
- 字符串每一个前缀子串的 π 值。
以字符串 aabaab 为例，π[i] 表示：字符串 s 长度为 i 的前缀，最长的 border 长度（最长真公共前后缀）。
| 下标（i） | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 前缀子串 | a | aa | aab | aaba | aabaa | aabaab |
| π | 0 | 1 | 0 | 1 | 2 | 3 |
原理：
技巧：
- 从大到小枚举字符串 s 某个前缀的所有 border。
假设我们此时生成了一个字符串 s 的前缀函数表，我们可以利用这张表，从大到小拿到某个前缀所有的 border。
原理就是 border 的传递性：字符串 border 的 border 还是 border。
到最后如果是没有 π 时，我们函数就会跳到我们提前给字符串预留的边界情况发生的 0 下标位置上。
string s;// 生成好的前缀函数int pi[N];// 长度为 i 的前缀中，所有 border 的长度voidget_border(int i){int j = pi[i];while(j){ cout << j; j = pi[j];}}三、计算前缀函数
我们在看完上面的内容后我们就来看看前缀函数怎么计算。
计算前缀函数：
- 计算前缀函数包含动态规划的思想，那就是推导状态转移方程。
对于字符串 s：
- 状态表示：
π[i] 表示：字符串 s 长度为 i 的前缀，最长的 border 长度（最长真公共前后缀）。
在计算完 i - 1 位置的前缀函数后，此时开始计算 i 位置的 π 值。
我们可以发现，我们 i 位置前上一个位置的真前缀和和真后缀和都存在 π[i - 1] 中。换句话说，如果 i 位置元素和 j 位置的元素相同，那就是 i 位置的 π 值了。
如果 i 和 j 不相同，我们可以继续往上一层的 π 值去寻找，也就是 π[ π [ i - 1 ] ]。
此时如果 s[ j -1 ] == s[ i ] ，此时便得出了 i 位置的 π 值了，否则我们在往下推。
- 状态转移方程：
- 我们发现，如果将长度为 i 的前缀中的 border 删去最后一个字符，就变成了长度为 i - 1 的前缀中的 border；
- 那么，我们就可以从大到小枚举长度为 i - 1 的前缀中所有的 border，然后判断这个 border 的下⼀个字符是否和 s[i] 相等：
a. 如果相等，说明这个就是最长的；
b. 如果不相等，那就继续判断下⼀个 border，直到将所有的 border 验证完毕。
string s;int pi[N];voidget_pi(int i){ cin >> s;int n = s.size(); s =' '+ s;for(int i =2; i <= n; i++){int j = pi[i -1];while(j && s[i]!= s[j +1]) j = pi[j];if(s[i]== s[j +1]) j++; pi[i]= j;}}当然，我们还可以进行优化，我们可以发现，当我们找到 i - 1 的时候，此时的 j 刚好就是在我们下一次要查找的 π 值。
string s;int pi[N];voidget_pi(int i){ cin >> s;int n = s.size(); s =' '+ s;for(int i =2, j =0; i <= n; i++){while(j && s[i]!= s[j +1]) j = pi[j];if(s[i]== s[j +1]) j++; pi[i]= j;}}时间复杂度：
模拟一遍过程会发现，指针每次向后移动一位后，指针最多会向后移动一位，然后继续往前跳。因此两个指针最差情况下会遍历字符串两遍，时间复杂度为 O(2n) = O(n)。
四、用前缀函数解决字符串匹配
设主串 S = “abcabaaaba”，模式串 T = “aba”，主串的长度为 n，模式串的长度为 m。
将两个字符串拼起来：S = T + ‘#’ + S = “aba#abcabaaaba”，对于新的字符串，可以在 O(n + m) 时间内生成前缀函数：
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| π | 0 | 0 | 1 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 |
前缀函数等于模式串长度的位置 i ，就是能够匹配的末端。在主串中，出现的位置就是 i − 2 × m 。那么，有了前缀函数之后，不仅能知道匹配了几次，还能知道每次匹配的起始位置。
注意：
当 i > m + 1 时，如果出现了 π == m 时，那就是出现了匹配的情况，匹配出现的位置为 i - 2 × m。例如上面 m == 3，π 为 3 都是匹配的，比如 i ==10、i == 14 的位置都能匹配上，它们分别对应主串的 4（10 - 2 × 3） 和 8（14 - 2 × 3）位置。
五、kmp 算法模板
题目来源： 洛谷
题目链接：P3375 【模板】KMP - 洛谷
【题目描述】
【输入格式】
【输出格式】
【示例】
我们按照上面的实现方式即可完成此题。
#include<iostream>#include<string>usingnamespace std;constint N =2e6+10; string s, t;int n, m;int pi[N];intmain(){ cin >> s >> t; n = s.size(); m = t.size(); s =' '+ t +'#'+ s;for(int i =2; i <= n + m +1; i++){int j = pi[i -1];while(j && s[j +1]!= s[i]) j = pi[j];if(s[j +1]== s[i]) j++; pi[i]= j;if(j == m){ cout << i -2* m << endl;}}for(int i =1; i <= m; i++) cout << pi[i]<<" "; cout << endl;return0;}六、next 数组版本
next 数组版本其实和上面是一样的，只不过是把上面的过程拆成两步来写：
- 先预处理模式串 t 的前缀函数 - next 数组；
- 在暴力匹配的过程中，用生成的 next 数组，加速匹配。
next 数组的本质也是求解我们的前缀函数。我们来举一个例子：
我们先把 t 的 next 数组求出来。
此时我们拿 t 来和 s 进行匹配。
当我们发现匹配不上的时候，如果是暴力匹配，那 t 就得从头开始继续往后匹配，但是由于我们求了 t 的前缀数组，所以我们可以利用数组来加速匹配。
#include<iostream>#include<string>usingnamespace std;constint N =2e6+10; string s, t;int n, m;int ne[N];intmain(){ cin >> s >> t; n = s.size(); m = t.size(); s =' '+ s; t =' '+ t;// 预处理模式串的 next 数组for(int i =2, j =0; i <= m; i++){while(j && t[i]!= t[j +1]) j = ne[j];if(t[i]== t[j +1]) j++; ne[i]= j;}// 利⽤ next 数组匹配for(int i =1, j =0; i <= n; i++){while(j && s[i]!= t[j +1]) j = ne[j];if(s[i]== t[j +1]) j++;if(j == m){ cout << i - m +1<< endl;}}for(int i =1; i <= m; i++) cout << ne[i]<<" "; cout << endl;return0;}七、周期和循环节
总结
以上便是 kmp 算法的原理啦，还是有一点点绕的，大家可以多琢磨琢磨，代码不是很难写，但是理解不容易，希望大家多加思考，我们下一章节再见。
🎇坚持到这里已经很厉害啦，辛苦啦🎇ʕ • ᴥ • ʔづ♡ど
