KMP算法：根据三位作者(D.E.Knuth，J.H.Morris和V.R.Pratt)名字来命名，全称是KnuthMorrisPratt算法，简称为KMP算法。
KMP算法核心思想：假设主串是a，模式串是b，在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望通过某种规律可以将模式串往后多滑动几位，跳过那些肯定匹配不上的情况，说白了就是高效关键字搜索。
在模式串和主串匹配的过程中，明确两个概念：
1、好前缀：把已经匹配的那段字符叫作好前缀
2、坏字符：把不能匹配的那个字符叫作坏字符
在模式串匹配主串的过程中，如果遇到了坏字符，我们就需要把模式串向后滑动，滑动过程中，当模式串和好前缀存在上下对应重合，对于前面几个字符的比较，就相当于使用好前缀的后缀子串跟模式串的前缀子串进行比较！这个比较能否更加高效？
KMP算法就是寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，可不可以寻找一种规律将模式串一次性滑动很多位？
解决方法只需拿到好前缀本身，然后在好前缀的所有后缀子串中，查找到最长的并且跟好前缀的前缀子串还要匹配的子串(最长可匹配后缀子串)。
最长可匹配后缀子串：在好前缀的所有后缀子串中，最长的可以匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串。
最长可匹配前缀子串：与最长可匹配后缀子串对应，叫最长可匹配前缀子串。
图解：如果最长的可匹配的前缀子串是{v}，长度是k，模式串一次性向后滑动j-k位，也就是在j的基础上减去了j-k，相当于每次遇到坏字符的时候就把j更新为k，i不发生变化，接着继续比较！
如何求好前缀的最长可匹配前缀和后缀子串呢？这个问题其实不涉及主串，只需要通过模式串本身就能求解。
模式串数组存储：
模式串与主串匹配过程图解：
第一个字符不匹配：不匹配字符前面没有字符，也就是说最长公共前后缀长度为0，那么直接将模式串向后移动一位。
用程序描述就是将模式串第一个字符与主串中当前位的下一位比较
第二个字符不匹配：不匹配字符前面只有一个字符，也就是说最长公共前后缀长度为0（最长公共前后缀长度一定小于好前缀长度），那么直接将模式串向后移动一位。
用程序描述就是将模式串第一个字符与主串中的当前位比较。
第三个字符不匹配：不匹配字符前面只有两个字符，也就是说最长公共前后缀长度为0（好前缀ab没有最长公共前后缀），那么直接将模式串向后移动两位。
用程序描述就是将模式串第一个字符与主串中的当前位比较
第四个字符不匹配：不匹配字符前面有三个字符，也就是说最长公共前后缀长度最大2，最小0（aba最长公共前后缀是a，长度1），那么直接将模式串向后移动两位。
用程序描述就是将模式串第二个字符与主串中的当前位比较
第五个字符不匹配：不匹配字符前面有四个字符，也就是说最长公共前后缀长度最大3，最小0（abab最长公共前后缀是ab，长度2），那么直接将模式串向后移动两位。
用程序描述就是将模式串第三个字符与主串中的当前位比较
第六个字符不匹配：不匹配字符前面有五个字符，也就是说最长公共前后缀长度最大4，最小0（ababa最长公共前后缀是aba，长度3），那么直接将模式串向后移动两位。
用程序描述就是将模式串第四个字符与主串中的当前位比较
最长公共前后缀长度图解：
总结：模式串和主串的比较满足这样的规律，求得好前缀最长公共前后缀长度n，模式串的第n+1个字符与主串中的坏字符（当前位）进行比较。
填表练一练：
next数组：
一只小跃跃