前言
今天看了July博主关于KMP算法的文章http://blog.csdn.net/v_july_v/article/details/7041827，写的很是深入浅出、浅显易懂，对于我这样的对KMP算法一知半解的小白来说获益匪浅。在此表示感谢，辛苦了！
下面是我看了 王红梅老师《算法设计与分析》的中关于next函数实现的一点小小感想，在此与大家分享，算是拿来主义吧^_^····
建议大家先将July博主的那边关于KMP算法仔细看下，启发还是很大的，虽然有了比KMP更高效的sunday 算法。
July文章中是先求出了“最大长度表”，然后通过向右“平移”首位补-1的方式求出，这种方式确实很直观很容易理解。
正文
我尽量说的浅显点，博主的语言表达能力欠佳啊·····┭┮﹏┭┮
还是先把程序贴出来吧，用java实现的，其实也就是将书中c++的描述，转换语言了一下而已。
测试用的模式串是：abcdabd，结果如下
下面我们讲讲next函数的原理，基是本将自己的理解表述出来，如有不当之处，还望指出
关于前、后缀可以理解为模式中的子串，只是位置不一样而已。
首先，设T是要求出next数组的模式串。假设，我们已经求出了next[0]、next[1]...next[j]的值（ps：next[j]是对应于T[j]的），那么如何求出next[j+1]的呢？
这时候我们可以设k = next[j]，（公式不好编辑啊····）
子串S1 ：T[0]...T[k-1]
子串S2 ：T[j-k]...T[j-1]
则S1 = S2，互为真前后缀。这时候就要比较T[k] 和T[j]。
(一)、若T[k]=T[j]，则next[j+1]=k+1.
(二)、若T[k]≠T[j]，此时就要找到 T[0]...T[j-1]的真前、缀和真后缀相等的第二大子串，比如模式abcdabcbc， 比如T[0]T[1]T[2]=abc 与T[4]T[5]T[6]=abc是当前相等最大的前、后缀，此时要求出next[6]的值，这时候就要比较TT[3]和T[6]，T[3]≠T[6]，这时候就要退回到T[0]T[1]T[2]中求出最大的前、后缀是T[0]T[1]= T[4]T[5]=ab。从而next[k]的值为T[0]...T[k-1]的真前、后缀的相等的最大子串的长度，则T[0]...T[next[k]-1]即为T[0]...T[j-1]的真前、后缀相等的第二大子串。
令k=next[k],再比较T[k]和T[j]，此时仍会出现两种情况：T[k]=T[j]和T[k]≠T[j]。
若T[k]=T[j]则按照（一）的方式处理；反之，则与（二）类似，在找出T[0]...T[j-1]的真前、后缀的相等的最大子串，重复（二）的过程，直到T[k]=T[j]或者next[k]=-1,如果T[0]...T[j-1]不存在真前、后缀相等的子串，此时next[j+1]=0.
这是代码：
package Array;
public class KMP_next {
public static void Next(String str, int[] next) {
int j = 0,k =-1;
int len = str.length();
next[0] = -1;
while(j < len-1){ //这个地方要注意是len-1 不是len，不然会数组越界的
if(k == -1){
next[++j] = 0;
k = 0;
} else if(str.charAt(j) == str.charAt(k)) { //确定next(j+1)的值
k++;
next[++j] = k;
} else {
k = next[k];
}
}
for(int i=0; i<next.length; i++) {
System.out.printf(next[i] + " ");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//String str = "abcdabd";
String str = "abcabcbc";
int[] next = new int[str.length()];
Next(str, next);
}
}
其实原理不是特别难，只是书中的描述大都过于理论了，所以我们才会觉得无从下手，如果耐下性子仔细琢磨琢磨你会发下其实也没那么高深。
ps:有空我会把公式和原理图添加上的