在大学的时候，应该在数据结构里面都看过kmp算法吧，不知道有多少老师对该算法是一笔带过的，至少我们以前是的，
确实kmp算法还是有点饶人的，如果说红黑树是变态级的，那么kmp算法比红黑树还要变态，很抱歉，每次打kmp的时候，输
入法总是提示“看毛片”三个字,嘿嘿，就叫“看毛片算法”吧。
一：bf算法
如果让你写字符串的模式匹配，你可能会很快的写出朴素的bf算法，至少问题是解决了，我想大家很清楚的知道它的时间复
杂度为o（mn），原因很简单，主串和模式串失配的时候，我们总是将模式串的第一位与主串的下一个字符进行比较，所以复杂
度高在主串每次失配的时候都要回溯，图我就省略了。
二：kmp算法
刚才我们也说了，主串每次都要回溯，从而提高了时间复杂度，那么能不能在“主串”和“模式串”失配的情况下，主串不回溯呢？
而是让”模式串“向右滑动一定的距离，对上号后继续进行下一轮的匹配，从而做到时间复杂度为o（m+n）呢？所以kmp算法就是
用来处理这件事情的，下面我们看下简单的例子。
通过这张图，我们来讨论下它的一般推理，假设主串为s，模式串为p，在si != pj的时候，我们可以看到满足如下关系式
si-jsi-j+1...sn-1=p0p1..pj-1。那么模式p应该向右滑动多少距离？也就是主串中的第i个字符应与模式串中的哪一个字符进行比较？
假设应该与模式串中的第k的位置相比较，假如模式串中存在最大的前缀真子串和后缀真子串，那么有p0p1..pk-1=pj-kpj-k+1...pj-1.
这句话的意思也就是说，在模式p中，前k个字符与j个字符之前的k个字符相同，比如说：“abad”的最大前缀真子串为“aba"，最大
后缀真子串为“bad”，当然这里是不相等，这里的0<k<j，我们希望k接近于j，那么我们滑动的距离将会最小，好吧，现在我们用
next[j]来记录失配时模式串应该用哪一个字符于si进行比较。
设 next[j]=k。根据公式我们有
-1 当j=0时
next[j] = max{k| 0<k<j 且 p0p1..pk-1=pj-kpj-k+1...pj-1}
0 其他情况
好，接下来的问题就是如何求出next[j],这个也就是kmp思想的核心，对于next[j]的求法，我们采用递推法，现在我们知道了
next[j]=k，我们来求next[j+1]=？的问题？其实也就是两种情况：
①：pk=pj 时 则p0p1...pk=pj-kpj-k+1...pj, 则我们知：
next[j+1]=k+1。
又因为next[j]=k，则
next[j+1]=next[j]+1。
②：pk!=pj 时 则p0p1...pk!=pj-kpj-k+1...pj,这种情况我们有点蛋疼，其实这里我们又将模式串的匹配问题转化为了上面我们提到
的”主串“和”模式串“中寻找next的问题，你可以理解成在模式串的前缀串和后缀串中寻找next[j]的问题。现在我们的思路就是一定
要找到这个k2，使得pk2=pj，然后将k2代入①就可以了。
设 k2=next[k]。 则有p0p1...pk2-1=pj-k2pj-k2+1...pj-1。
若 pj=pk2， 则 next[j+1]=k2+1=next[k]+1。
若 pj!=pk2, 则可以继续像上面递归的使用next，直到不存在k2为止。
好，下面我们上代码，可能有点绕，不管你懂没懂，反正我懂了。
