KMP算法求next数组的一些理解

看了一天的KMP算法，终于对其有所理解，下面是对该算法的理解，希望对初学该算法的同学有所帮助。

net函数的求解

先看算法：

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，那只能继续从字串的字串中找了。