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（）一題。