KMP算法之理解

以下对于KMP算法的理解，是在拜读各路牛人大作之后 ，基于个人的习惯思路的总结，试图还原KMP算法的设计出发点与思路。
基于朴素的字符串匹配算法，KMP算法要避免每一次暴力的回溯，简化时间复杂度，就需要找到模式串本身的特点，利用这些特点简化匹配算法，于是，要解决的核心问题就是：
1.找到模式串T中的最大前后缀公共元素长度；
2.根据该长度，判断可以将模式串T右移多少位进行下一轮匹配
这两个问题又有两个关键要素：
1.如何求最大前后缀公共元素长度？（以及由此推出next数组）
2.如何求解进行下一轮匹配的模式串右移位数，找到其与最大前后缀公共元素长度的关系 ？
两个问题一个一个来：
（一）最大前后缀公共元素长度与next数组
根据july的文章《从头到尾彻底理解KMP算法》，我们不难理解最大前后缀公共元素长度的人工求法，并由此推出next[j]的值，next[j]的值，表示前j-1个元素的最大前后缀公共元素长度（各元素最大前后缀公共元素长度初值-1的右移）。那如何用计算机快速的求出next数组呢？
参照http://www.cnblogs.com/c-cloud/p/3224788.html 博客中这位同学的思路,从数学归纳法的方法出发，来解决这个问题。
假如如图1，显然next[q]=k,要求next[q+1],即求q的最大前后缀公共元素长度，如下:

1. 　　已知前一步计算时最大相同的前后缀长度为k（k>0），即P[0]···P[k-1]；
2. 　　此时比较第k项P[k]与P[q],如图1所示
3. 　　如果P[K]等于P[q]，那么很简单，next[q+1]=++k;
4. 　　关键！关键有木有！关键如果不等呢？？？那么我们应该利用已经得到的next[0]···next[k]来求P[0]···P[k-1]这个子串中最大相同前后缀，可能有同学要问了——为什么要求P[0]···P[k-1]的最大相同前后缀呢？？？是啊！为什么呢？ 原因在于P[k]已经和P[q]失配了，而且P[q-k] ··· P[q-1]又与P[0] ···P[k-1]相同，看来P[0]···P[k-1]这么长的子串是用不了了，那么我要找个次长的子串即P[0]···P[j-1]，保证P[0]...P[j-1]与 P[k-j]...P[k-1]相同，即(j==next[k]==前k-1个元素的最大前后缀公共元素长度)，看看它的下一项P[j]是否能和P[q]匹配。如图2所示
5. （关于“次长”的理解：P[q]是还未参与过匹配的，所以要寻找q元素的最大前后缀，势必先要找到q-1的最大前后缀，然后q-1的最大前后缀k——表示失配了，所以，需要从k个元素中再找出最大前后缀j，再往后推导，这是一种递归关系。令j=next[k]，就不可能找出比j再大的索引完成q元素的最大前后缀）

据此，可以写出求next数组的代码，关于next数组，肯能在不同的理解上有不同的定义，此处仅根据july作者的理解来计算

（二）根据以上next的定义与计算，找到模式匹配下一轮匹配，模式串要右移的位数

假设现在已经匹配到 T[j]的位置失配，即T[j]!=S[i],那么模式串需要右移j-next[j]位再进行匹配，为什么？
可以用反证法证明，
设next[j]=k,假设，存在q，使得模式串右移j-q位，依然能匹配，q>k（意思是少移动几位），即：
若移动j-q位模式串匹配  <==> T[0]...T[q-1] == T[j-q]...T[j-1] ,q>k
而由于next[j]=k,
T[0]...T[k-1]==T[j-k]...T[j-1]  ,由于是最大前后缀公共元素长度，所以==> 对任意正数n，都有T[0]...T[k-1+n] != T[j-k-n]...T[j]
所以，T[0]...T[q-1] == T[j-q]...T[j-1] ,q>k 不成立，即移动j-q位，模式串不可能匹配，必须要从j-next[j]位再进行匹配
。图示如下：（待补充）