企业官网建设流程全解析

一文搞懂KMP算法（图解）

什么是KMP

• KMP算法是一种高效的字符串匹配算法，由Knuth、Morris和Pratt三位科学家共同提出，其核心思想是利用已匹配的信息避免不必要的回溯

接下来我将详细解释该算法的构建过程

用到这个算法有个很经典的题目，就是在文本串中找到一个模式串，例如在aabaabaafa（文本串）中找到aabaaf（模式串）；

可以看出，我们遍历到文本串中第六个字符b 和 模式串的第六个字符f不匹配了，如果采用暴力解法，此时就要从头匹配了，但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配

如图，画箭头的部分就是最长相等前后缀字符串，我们按照前缀表会自动重新匹配，也就是第三行这个位置，因为我们的f不匹配，但f之前的元素是匹配的，因此找到f之前和从开头开始相同的最大长度字符串，就可以获得更快解法

因此前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置

如何构造前缀表

• 前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相等前缀后缀

这里字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串，

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

我们这里构造的前缀表是最长相同前后缀的长度

例如字符串a的最长相等前后缀为0， 字符串aa的最长相等前后缀为1， 字符串aaa的最长相等前后缀为2

接下来就是构建前缀表了：

首先我们要解释一下next数组就可以是前缀表，但是很多地方都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组，这只是实现的方式不同，但是核心思想是一样的，本文为了方便理解，就以原本前缀表为例，我们先看看代码，再进行逐行解释

voidgetnext(int*next,conststring*s){intj=0;next[0]=0;for(inti=1;i<len;i++){while(j>0&&s[i]!=s[j]){j=next[j-1];}if(s[i]==s[j]){j++;}next[i]=j;}}

由于刚开始字符串长度为一，没有相同前后缀，所以next[0] = 0;

接下来i指向后缀末尾位置，j指向前缀末尾位置，我们直接从索引为1的位置开始遍历

我们可以看到当i = 1j = 0时s[i] == s[j]；则执行j++,next[1] = 1;

我们可以看到当i = 2j = 1时s[i] != s[j]；此时我们要进行回退操作，也就是我认为该算法中最精妙的部分，执行while循环，使j = next[j - 1]；

我们知道前缀表记录了该元素前最长的相同前后缀的长度，我们当前使用的是j对应的前缀长度，我们在继续扩张，但当我们不能继续匹配时，我们回到上一个元素的前缀表对应元素，继续扩张

同时前缀和对应的数字正好是我们要重新匹配元素的下标此时j = next[0]j = 0得到s[j] != s[i]，但此时j = 0不会再进入while循环，这也保证了next数组中数据大于0

则next[2] = 0；

我们继续j = 0i = 3

此时发现s[i] == s[j]则执行if语句，j++，next[3] = 1

继续j = 1i = 4

发现s[i] == s[j]则执行if语句，j++，next[4] = 2

继续j = 2i = 5

此时s[i] != s[j]又回进行一系列回退操作，j = next[j - 1]j = 1

s[i] != s[j]，j = next[j - 1]j = 0

至此next[5] = 0;

则next数组如下

想必此时你已经彻底明白了前缀表的构造，下面是前缀表进行减一的操作，只是实现方式有区别

voidgetnext(int*next,conststring*s){intj=-1;next[0]=-1;for(inti=1;i<len;i++){while(j>=0&&s[i]!=s[j+1]){j=next[j];}if(s[i]==s[j+1]){j++;}next[i]=j;}}

减一的操作你可以自己模拟一下过程就明白了，本质是一样的

接下来就是如何用这张表了，我这里还是以原本的前缀表进行演示

如何使用前缀表

依旧先来看一下代码的实现

为了方便展示，我们这里以力扣的28题为例

[28. 找出字符串中第一个匹配项的下标]

intstrStr(char*haystack,char*needle){intlenm=strlen(needle);intlen=strlen(haystack);if(lenm==0){return0;}if(len<lenm){return-1;}intnext[lenm];memset(next,0,sizeof(next));intj=0;next[j]=j;for(inti=1;i<lenm;i++){while(j>0&&needle[i]!=needle[j]){j=next[j-1];}if(needle[i]==needle[j]){j++;}next[i]=j;}j=0;for(inti=0;i<len;i++){while(j>0&&haystack[i]!=needle[j]){j=next[j-1];}if(haystack[i]==needle[j]){j++;}if(j==lenm){returni-j+1;}}return-1;}

其实你可以发现匹配的过程和构造前缀表时的思路一样，只不过这次移动的是模式串，我们就简单来说一下

依旧是以上文的那个字符串为例

当i = 5时，haystack[i] != needle[j]，则执行j = next[j - 1]，j = 2

继续遍历可以得到模式串，到此相比你对KMP算法已经有了一定的了解，快去试试吧