2023-01-23-图解KMP算法,带你彻底吃透KMP
图解KMP算法，带你彻底吃透KMP
模式串匹配——KMP算法
KMP算法 一直是一个比较难以理解的算法，本篇文章主要根据 中关于KMP算法的讲解，结合自己的思考，对于KMP算法进行一个比较详细的解释。
由于博主本人水平有限，难免会出现一些错误。如果发现文章中存在错误敬请批评指正，感谢您的阅读。
字符串模式匹配介绍
相信学习过数据结构与算法的同学一定不会对字符串感到陌生，字符串的逻辑结构与线性表很类似，不同之处是字符串中的元素都是字符。对于字符串这一数据结构，寻找字符串中子串的位置是最重要的操作之一，查找字串位置的操作通常称为 串的模式匹配 。而KMP算法就是一种字符串模式匹配算法，在介绍KMP算法之前，我们首先了解以下朴素的模式匹配算法是怎样进行的。
朴素的模式匹配算法
假设我们的主串S=“goodgoogle”，子串T=“google”，我们需要在主串中找到子串的位置，比较朴素的想法是用两个指针(指针其实也就是下标i,j)分别指向主串和子串，如果两个指针指向的元素相同则指针后移，不相同则需要回退指针( 主串指针回退到上次匹配首位的下一个位置，子串指针回退到开头位置 )，重复进行上述操作直到主串指针指向主串末尾，即如下所示：
(1) 从主串S的第一位开始，S与T的前三位都匹配成功，第四位匹配失败，此时将主串的指针退回到第二位，子串的指针退回子串开始，即从S[1]开始重新匹配。
(2) 主串S从第二位开始于子串T匹配，第一步就匹配失败，将主串指针指向第三位S[2]，子串指针指向开头，继续匹配。
(3) 同步骤二，第一步就匹配失败，将主串指针移动到第四位S[3]，子串指针指向开头，继续匹配。
(4) 还是第一步就匹配失败，将主串指针移动到第五位S[4]，子串指针指向开头，继续匹配。
(5) 到步骤5终于第一步能够匹配上，从S[4]开始指针依次向后移动，六个字母全部匹配上，匹配成功！
根据上面的步骤，我们可以得出朴素模式匹配算法的代码如下所示：
int find_sub_string(string s, string t)
{
int i = 0, j = 0; //初始化两个指针
while(i<s.size() && j<t.size()){
if(s[i] == t[j]){
i++; //如果两个指针指向的字符相等
j++; //则将两个指针向后移动
}
else{
i = i - j + 1; //匹配失败，i退回到上次匹配首位的下一位
j = 0; //j退回到子串首位
}
}
if(j>=t.size()){ //j走到子串末尾说明匹配成功
return i - j; //匹配成功返回主串中子串出现的第一位
}
else
return -1; //匹配失败，返回-1
}既然是朴素(暴力)解法，那必然存在时间复杂度的问题，我们不妨分析以下上述算法的时间复杂度。
最好的情况是一开始就匹配成功了，如主串为"googlegood"，子串为"google"，此时的时间复杂度为 O(m) (m为子串长度)
那么最坏的情况是什么呢？最坏的情况就是每次不成功的匹配都发生在子串末尾，就如 书中的例子，主串为S=“00000000000000000000000000000000000000000000000001”，子串为T=“0000000001”，推导一下可得此时的时间复杂度度为 *O((n-m+1)m) (n为主串长度)。
而在计算机中对字符的存储采用的是ASCII码，字符串可以看成是许许多多个0和l组成，因此这种最坏的情况是很可能出现的，在计算机的运算当中，模式匹配操作可以说是随处可见。这样看来，这个如此频繁使用的算法，朴素做法显得太低效了。
KMP算法
为了避免朴素算法的低效，几位计算机科学家辈D.E.Knuth、J.H.MorTis和V.R.Pratt发表了一个模式匹配算法，可以一定程度上避免重复遍历的问题，该算法就是大名鼎鼎的 KMP算法 。
从暴力匹配到KMP
要理解KMP算法的原理，我们首先需要批判一下朴素算法中有哪些做的不好的地方。
我们将之前的朴素算法的匹配过程合起来看如下面的图所示：
我们可以发现，在2、3、4步骤中，主串的首字符与子串的首字符均不等。我们仔细观察可以发现，对于子串"google"来说，首字母"g"与后面的两个字母是不相等的，而在步骤1中主串与子串的前三个字符相等，这就意味着子串的首字符"g"不可能与主串的二、三位相等，故上图中步骤2、3完全是多余的。
也就是说，如果我们知道子串的首字符"g"与后面两个字符不相等(此处需要进行一些预处理，这是后面的重点)，我们就不需要再进行2、3步操作，只保留1、4、5步即可。
从上面这幅图我们可以惊喜地发现，在使用朴素算法进行匹配时，主串指针需要进行一些回退；而在知道了子串的一些性质后，主串指针不需要再进行回退，只需一直往前走就行，这样就节省了一些时间开销。
你或许还会有疑问，主串指针是不需要回退了，但为啥我的子串指针还要一直回退到开头呢，有没有办法避免这样呢？
当然是有的，我们再举一个例子，假设主串S=“abcababca”,子串T=“abcabx”，那我们采用朴素算法在进行模式匹配的步骤如下所示：
由之前一个例子的分析可知由于T串的首字母"a"与之后的字母"b"、“c"不等，故步骤2、3均是可以省略的。
又因为T的首位"a"与T第四位的"a"相等，第二位的"b"与第五位的"b"相等。而在步骤1中，第四位的"a"与第五位的"b"已经与主串s中的相应位置比较过了是相等的。因此可以断定, T的首字符“a”、第二位的字符“b”与S的第四位字符和第五位字符也不需要比较了，肯定也是相等的。所以步骤4、5这两个比较得出字符相等的步骤也可以省略。
所以在这个例子中我们模式匹配的流程为：
68747470733a2f2f62:6c6f672e6373646e2e6e65742f71715f34333836393130362f:61727469636c652f64657461696c732f313238373533353237