【算法详解】理解KMP，真的那么难吗？—— 一篇讲透它的核心思想

🫧 励志不掉头发的内向程序员：个人主页
 ✨️ 个人专栏: 《C++语言》《Linux学习》

🌅偶尔悲伤，偶尔被幸福所完善

👓️博主简介:

文章目录

• 前言
• 一、相关概念
• 二、前缀函数
• 三、计算前缀函数
• 四、用前缀函数解决字符串匹配
• 五、kmp 算法模板
• 六、next 数组版本
• 七、周期和循环节
• 总结

前言

本文用尽量详细的语言来讲解说明 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 长度（最长真公共前后缀）。

原理：

技巧：

• 从大到小枚举字符串 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：

1. 状态表示：
   π[i] 表示：字符串 s 长度为 i 的前缀，最长的 border 长度（最长真公共前后缀）。

在计算完 i - 1 位置的前缀函数后，此时开始计算 i 位置的 π 值。

我们可以发现，我们 i 位置前上一个位置的真前缀和和真后缀和都存在 π[i - 1] 中。换句话说，如果 i 位置元素和 j 位置的元素相同，那就是 i 位置的 π 值了。

如果 i 和 j 不相同，我们可以继续往上一层的 π 值去寻找，也就是 π[ π [ i - 1 ] ]。

此时如果 s[ j -1 ] == s[ i ] ，此时便得出了 i 位置的 π 值了，否则我们在往下推。

2. 状态转移方程：

• 我们发现，如果将长度为 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) 时间内生成前缀函数：

前缀函数等于模式串长度的位置 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 数组版本其实和上面是一样的，只不过是把上面的过程拆成两步来写：

1. 先预处理模式串 t 的前缀函数 - next 数组；
2. 在暴力匹配的过程中，用生成的 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 算法的原理啦，还是有一点点绕的，大家可以多琢磨琢磨，代码不是很难写，但是理解不容易，希望大家多加思考，我们下一章节再见。

🎇坚持到这里已经很厉害啦，辛苦啦🎇ʕ • ᴥ • ʔづ♡ど