KMP算法详解

什么是KMP

说到KMP，先说一下KMP这个名字是怎么来的，为什么叫做KMP呢。
因为是由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP

KMP有什么用

KMP主要应用在字符串匹配上
KMP的主要思想是：当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了
所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任

什么是前缀表

写过KMP的同学，一定都写过next数组，那么这个next数组究竟是个啥呢？
next数组就是一个前缀表（prefix table）
前缀表有什么作用呢？
前缀表是用来回溯的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配
为了清楚的了解前缀表的来历，我们来举一个例子：
要在文本串：aabaabaafa中查找是否出现过一个模式串：aabaaf
请记住文本串和模式串的作用，对于理解下文很重要，要不然容易看懵
如动画所示：

动画里，特意把子串**aa**标记上了，这是有原因的，大家先注意一下，后面还会说道
可以看出，文本串中第六个字符b和模式串的第六个字符f，不匹配了。如果暴力匹配，会发现不匹配，此时就要从头匹配了
但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配
那么前缀表是如何进行记录的呢
首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，在重新匹配，此也意味着在某个字符匹配失败时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。
那么什么是前缀表：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀

为什么一定要用前缀表

刚刚匹配的过程在下标为5的地方匹配失败，模式串是指向f，如图：

然后就找到了下标2，指向b，继续匹配，如图：

以下这句话，对于理解为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配非常重要！
下标5之前这部分的字符串（也就是字符串**aabaa**）的最长相等的前缀和后缀字符串是子字符串**aa**，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了
所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

如何计算前缀表

接下来就要说一说怎么计算前缀表
如图：

长度为前1个字符的子串a，最长相同前后缀的长度为0。（注意这里计算相同前后缀，不算重复的字符）

长度为前2个字符的子串aa，最长相同前后缀的长度为1

长度为前3个字符的子串aab，最长相同前后缀的长度为0

以此类推：

• 长度为前4个字符的子串aaba，最长相同前后缀的长度为1
• 长度为前5个字符的子串aabaa，最长相同前后缀的长度为2
• 长度为前6个字符的子串aabaaf，最长相同前后缀的长度为0

那么把求得的最长相同前后缀的长度就是对应前缀表的元素，如图：

可以看出：前缀表里的数值代表着就是：当前位置之前的子串有多大长度相同的前缀后缀
再来看一下如何利用前缀表找到当字符不匹配的时候应该指针应该移动的位置。如动画所示：

找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少
为什么要看前一个字符的前缀表的数值呢，因为要找前面字符串的最长相同的前缀和后缀，所以要看前一位的前缀表的数值
前一个字符的前缀表的数值是2，所以把下标移动到下标为2的位置继续比配
最后就在文本串中找到了和模式串匹配的子串了

前缀表有什么问题

来看一下刚刚求的这个前缀表有什么问题呢？
如图：

看这个位置红框的位置，如果要找下标1所对应前缀表里的数值的时候，前缀表里的数值依然是1，然后就要跳到下标1的位置，如此就形成了一个死循环
如何避免呢，就把前缀表里的数值统一减一， 开始位置设置为-1 。 这一点对理解后面KMP代码很重要！！
改为如图所示：

这样就避免的死循环，只不过后续取前缀表里的数值的时候，要记得再+1，才是我们想要的值
最后得到的新前缀表在KMP算法里通常用一个next数组来表示
注意这个next数组就根据模式串求取的

使用next数组来匹配

有了next数组，就可以根据next数组来匹配文本串s，和模式串t了
注意next数组是新前缀表（旧前缀表统一减一了）
匹配过程动画如下：

时间复杂度分析

再来看一下时间复杂度， 假设文本串长度为n，模式串长度为m，动画为上图
其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是，但之前还要单独生成next数组，时间复杂度是，整个KMP算法的时间复杂度是
暴力的解法显而易见是，所以KMP在字符串匹配中极大的提高的搜索的效率

总结

• 本篇我们介绍了什么是KMP，KMP可以解决什么问题，然后分析KMP算法里的next数组，知道了next数组就是前缀表，再分析为什么要是前缀表而不是什么其他表
• 接着从给出的模式串中，我们推导出了前缀表，后来又发现前缀表有问题，然后就把前缀表里数值统一减一，得到的新前缀表就是 next数组
• 分析了KMP算法的时间复杂度，并且和暴力方法做了对比
• 最后用next数组，求得文本串s里是否出现过模式串t