KMP算法学习笔记

KMP简介

KMP 算法（Knuth-Morris-Pratt algorithm），又称字符串匹配算法，是一种用于在字符串中查找子字符串的算法。它是由 Donald Knuth、Morris 和 Pratt 于 1970 年代共同开发的。可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配。

KMP 算法的应用

KMP 算法在文本处理领域有着广泛的应用，以下是一些常见的应用场景：

• 文本编辑器中的搜索和替换功能：KMP 算法可以用于快速查找文本中的特定模式，从而实现高效的搜索和替换功能。

• 生物信息学中的 DNA 序列分析：KMP 算法可以用于快速查找 DNA 序列中的特定模式，例如基因、蛋白质编码区等。

• 数据压缩中的模式匹配：KMP 算法可以用于在数据压缩算法中进行模式匹配，例如 LZW 压缩算法。

• 网络安全中的入侵检测：KMP 算法可以用于在网络流量中检测恶意模式，例如病毒、木马等。

KMP 算法在前端的应用

在前端领域，KMP 算法也有一些应用场景，例如：

• 代码高亮：KMP 算法可以用于快速匹配代码中的关键字、函数名、变量名等，从而实现代码高亮功能。
  

• 文本编辑器中的智能提示：KMP 算法可以用于在文本编辑器中实现智能提示功能，例如根据用户输入的文本提供可能的补全内容。

• 路由系统：在前端路由系统中，有时需要根据URL来匹配相应的路由，KMP算法可以用于实现这种匹配。

• 数据过滤和处理：在处理用户输入或者从服务器返回的数据时，有时需要匹配特定的模式，例如过滤敏感词汇等，KMP算法可能会派上用场。

• 搜索功能：在前端应用中实现搜索功能时，可能需要在文本中快速找到匹配的字符串，KMP算法可以用来实现这一点。

• 正则表达式引擎：KMP 算法可以用于实现正则表达式的匹配引擎，从而支持正则表达式在前端中的应用。

前端是否需要学习 KMP 算法

KMP 算法是一门较为复杂的算法，对于大多数前端开发人员来说，学习它并非必需。如果你的工作或者项目中需要处理大量字符串匹配的任务，那么学习KMP算法是有益的。

• 前端性能优化：如果需要对前端代码进行性能优化，那么了解 KMP 算法可以帮助开发人员识别和优化与字符串匹配相关的性能瓶颈。

• 开发文本编辑器或代码编辑器：如果需要开发文本编辑器或代码编辑器，那么学习 KMP 算法可以帮助开发人员实现更强大和高效的搜索、替换和代码高亮功能。

• 开发正则表达式引擎：如果需要开发正则表达式引擎，那么学习 KMP 算法是必需的。

KMP 算法解读

KMP算法的核心，是一个被称为部分匹配表(Partial Match Table)的数组。

建议推荐阅读：如何更好地理解和掌握 KMP 算法? - 阮行止的回答 - 知乎  或者 https://www.bilibili.com/video/BV1Lw4m1X7m5/

字符串匹配问题

我们先从最朴素的Brute-Force算法开始讲起。

Brute-Force

Brute-Force是一个纯暴力算法。

最朴素的思想，就是从前往后逐字符比较，一旦遇到不相同的字符，就返回False；如果两个字符串都结束了，仍然没有出现不对应的字符，则返回True。实现如下：

Brute-Force 慢得像爬一样。它最坏的情况就是 O(nm），如下图所示：

在 Brute-Force 中，如果从 S[i] 开始的那一趟比较失败了，算法会直接开始尝试从 S[i+1] 开始比较。这种行为，属于典型的“没有从之前的错误中学到东西”。我们应当注意到，一次失败的匹配，会给我们提供宝贵的信息——如果 S[i : i+len(P)] 与 P 的匹配是在第 r 个位置失败的，那么从 S[i] 开始的 (r-1) 个连续字符，一定与 P 的前 (r-1) 个字符一模一样！

跳过不可能成功的字符串比较

优化 Brute-Force 的路线是“尽量减少比较的趟数”，而如果我们跳过那些绝不可能成功的字符串比较，则可以希望复杂度降低到能接受的范围。

那么，哪些字符串比较是不可能成功的？来看一个例子。已知信息如下：

这里可以阅读：如何更好地理解和掌握 KMP 算法? - 灵茶山艾府的回答 - 知乎 、如何更好地理解和掌握 KMP 算法? - 海纳的回答 - 知乎，理解

• 如何找到乙回退的位置？
  

• 最大匹配数为？次大匹配了多少呢？

• 理解PMT的

PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。

主字符串"ababababca"中查找模式字符串"abababca"，

其前缀集合与后缀集合的交集的最长元素为”abab”， 长度为4。所以就可以断言，主字符串中i指针之前的 4 位一定与模式字符串的第0位至第 4 位是相同的，即长度为 4 的后缀与前缀相同。这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持i指针不动，然后将j指针指向模式字符串的PMT[j −1]位即可。

以图中的例子来说，在 i 处失配，那么主字符串和模式字符串的前边6位就是相同的。又因为模式字符串的前6位，它的前4位前缀和后4位后缀是相同的，所以我们推知主字符串i之前的4位和模式字符串开头的4位是相同的。就是图中的灰色部分。那这部分就不用再比较了。

有了上面的思路，我们就可以使用PMT加速字符串的查找了

带着“跳过不可能成功的尝试”的思想，我们来看next数组。

next数组

next数组是对于模式串而言的。P 的 next 数组定义为：next[i] 表示 P[0] ~ P[i] 这一个子串，使得 前k个字符恰等于后k个字符 的最大的k. 特别地，k不能取i+1（因为这个子串一共才 i+1 个字符，自己肯定与自己相等，就没有意义了）。

上图给出了一个例子。P="abcabd"时，next[4]=2，这是因为P[0] ~ P[4] 这个子串是"abcab"，前两个字符与后两个字符相等，因此next[4]取2. 而next[5]=0，是因为"abcabd"找不到前缀与后缀相同，因此只能取0. 　　如果把模式串视为一把标尺，在主串上移动，那么 Brute-Force 就是每次失配之后只右移一位；改进算法则是每次失配之后，移很多位，跳过那些不可能匹配成功的位置。但是该如何确定要移多少位呢？

图给出了一个例子。P="abcabd"时，next[4]=2，这是因为P[0] ~ P[4] 这个子串是"abcab"，前两个字符与后两个字符相等，因此next[4]取2. 而next[5]=0，是因为"abcabd"找不到前缀与后缀相同，因此只能取0. 　　如果把模式串视为一把标尺，在主串上移动，那么 Brute-Force 就是每次失配之后只右移一位；改进算法则是每次失配之后，移很多位，跳过那些不可能匹配成功的位置。但是该如何确定要移多少位呢？

在 S[0] 尝试匹配，失配于 S[3] <=> P[3] 之后，我们直接把模式串往右移了两位，让 S[3] 对准 P[1]. 接着继续匹配，失配于 S[8] <=> P[6], 接下来我们把 P 往右平移了三位，把 S[8] 对准 P[3]. 此后继续匹配直到成功。　　我们应该如何移动这把标尺？很明显，如图中蓝色箭头所示，旧的后缀要与新的前缀一致（如果不一致，那就肯定没法匹配上了）！　　回忆next数组的性质：P[0] 到 P[i] 这一段子串中，前next[i]个字符与后next[i]个字符一模一样。既然如此，如果失配在 P[r], 那么P[0]~P[r-1]这一段里面，前next[r-1]个字符恰好和后next[r-1]个字符相等——也就是说，我们可以拿长度为 next[r-1] 的那一段前缀，来顶替当前后缀的位置，让匹配继续下去！　　您可以验证一下上面的匹配例子：P[3]失配后，把P[next[3-1]]也就是P[1]对准了主串刚刚失配的那一位；P[6]失配后，把P[next[6-1]]也就是P[3]对准了主串刚刚失配的那一位。

如上图所示，绿色部分是成功匹配，失配于红色部分。深绿色手绘线条标出了相等的前缀和后缀，其长度为next[右端]. 由于手绘线条部分的字符是一样的，所以直接把前面那条移到后面那条的位置。因此说，next数组为我们如何移动标尺提供了依据。接下来，我们实现这个优化的算法。

利用next数组进行匹配

了解了利用next数组加速字符串匹配的原理，我们接下来代码实现之。分为两个部分：建立next数组、利用next数组进行匹配。

首先是建立next数组。我们暂且用最朴素的做法，以后再回来优化：

如上图代码所示，直接根据next数组的定义来建立next数组。不难发现它的复杂度是的。

接下来，实现利用next数组加速字符串匹配。代码如下：

如何分析这个字符串匹配的复杂度呢？乍一看，pos值可能不停地变成next[pos-1]，代价会很高；但我们使用摊还分析，显然pos值一共顶多自增len(S)次，因此pos值减少的次数不会高于len(S)次。由此，复杂度是可以接受的，不难分析出整个匹配算法的时间复杂度：O(n+m).

快速求next数组

终于来到了我们最后一个问题——如何快速构建next数组。

首先说一句：快速构建next数组，是KMP算法的精髓所在，核心思想是“P自己与自己做匹配”。

为什么这样说呢？回顾next数组的完整定义：

• 定义 “k-前缀” 为一个字符串的前 k 个字符； “k-后缀” 为一个字符串的后 k 个字符。k 必须小于字符串长度。

•  next[x] 定义为： P[0]~P[x] 这一段字符串，使得k-前缀恰等于k-后缀的最大的k.　

这个定义中，不知不觉地就包含了一个匹配——前缀和后缀相等。接下来，我们考虑采用递推的方式求出next数组。如果next[0], next[1], ... next[x-1]均已知，那么如何求出 next[x] 呢？

来分情况讨论。

首先，已经知道了 next[x-1]（以下记为now），如果 P[x] 与 P[now] 一样，那最长相等前后缀的长度就可以扩展一位，很明显 next[x] = now + 1. 图示如下

刚刚解决了 P[x] = P[now] 的情况。那如果 P[x] 与 P[now] 不一样，又该怎么办？

如图。长度为 now 的子串 A 和子串 B 是 P[0]~P[x-1] 中最长的公共前后缀。可惜 A 右边的字符和 B 右边的那个字符不相等，next[x]不能改成 now+1 了。因此，我们应该缩短这个now，把它改成小一点的值，再来试试 P[x] 是否等于 P[now].

now该缩小到多少呢？显然，我们不想让now缩小太多。因此我们决定，在保持“P[0]~P[x-1]的now-前缀仍然等于now-后缀”的前提下，让这个新的now尽可能大一点。 P[0]~P[x-1] 的公共前后缀，前缀一定落在串A里面、后缀一定落在串B里面。换句话讲：接下来now应该改成：使得 A的k-前缀等于B的k-后缀 的最大的k.

您应该已经注意到了一个非常强的性质——串A和串B是相同的！B的后缀等于A的后缀！因此，使得A的k-前缀等于B的k-后缀的最大的k，其实就是串A的最长公共前后缀的长度 —— next[now-1]！

来看上面的例子。当P[now]与P[x]不相等的时候，我们需要缩小now——把now变成next[now-1]，直到P[now]=P[x]为止。P[now]=P[x]时，就可以直接向右扩展了。

参考文章：

如何更好地理解和掌握 KMP 算法? - 阮行止的回答 - 知乎

转载本站文章《KMP算法学习笔记》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/PatternMatching/9106.html