KMP算法中的Next数组的求取

本文针对博客中下部链接：

点击打开链接

的内容，进行补充。

主要是如何计算Next数组，通过计算得到的next数组，可以轻松计算，每次移动的位数，代码如下：

void getNext(const char * ss, int len){
	//int next[9];
	int  j = -1,  i = 0;

	Next[0] = -1;
	while(i < len)
	{
			  if(j == -1 || ss[i] == ss[j])
			 {

						i++;
						j++;
						Next[i] = j;
			 }
			 else
			{
					   j = Next[j];
			}
	}
	/*for(int i=0;i<len+1;++i)
		printf("%d ",Next[i]);*/
	return;
}
           

ss表示模式字符串首地址，len表示模式字符串的长度（不包括‘\0’）

函数最后得到的数组大小是len+1，例如模式串为“aabb”，那么next数组等于[-1,0,1,0,0]，其中0,1,0,0分别对应aabb，-1表示没有一个配准的情况，依然有用，具体用法，可以参见Leetcode的Implemented strStr（）一题。