看了一天的KMP算法，终于对其有所理解，下面是对该算法的理解，希望对初学该算法的同学有所帮助。
先看算法：
public static int[] getNext(int[] p) { int i,j,slen; slen = p.Length; int[] next = new int[slen]; netxt[0] = -1; j = -1; while(i<slen) { if(j==-1||p[i]==p[j]) { ++i,++j,next[i]=j; } else { j = next[j]; } } return next; }对于这个算法的难点在于，如果对于下一个next值（其中 p[i]!=p[j]的情况）该怎样求解 即我们已知next[i] = k，同时p[k]!=p[i],求next[i+1] 由此我们可知：p[i1] =p[i-k+i1] i1 = 0,,,k-1 既然p[k]!=p[i] 那么，next[i]的最大值只可能是next{k} +1,为什么，让我们来证一下。 证明： 既然p[k]!=p[i],那么，要想找到对称串，与p[i]相等的也只能在索引k前面找了。（不然，next(i)就大于k了） 我们设p[i2] = p[i]那么此时显然{p[0],p[1],…,p[i2]}就是我们要找的对称串，则next(i+1)=i2+1 则，由此推论：p[i1]=p[i-i2+i1] (i1=0,1,…i2-1) 又因为p[i1] =p[i-k+i1] i1 = 0,,,k-1（上面的条件）, 可以知道p[i-i2+i1]=p[i-k+i1]（i1=0,1,…,i2-1） 进而可知p[i1] = p[k-i2+i1] (i1=0,1,…,i2-1) 则{p[0],p[1],…,p[i2-1]就是{p[0],p[1],…,p[k-1]}的对称串 即next(k) = i2则next(i+1) = next(k)+1 故得证 因此，如果不是相应的next(k)+1，那只能继续从字串的字串中找了。
