kmp入門了解（多種求next數組樣例詳解）

我看到的大神的從入門到深刻了解連結比我講述的更為透徹

原文：https://blog.csdn.net/v_july_v/article/details/7041827

下面是我的對于kmp見解

kmp含義：

在我看來kmp說簡單點就是求在母串中子串出現的位置；解題的關鍵就在于就求子串的相同的字首和字尾用next數組存儲在第i個字元（包含第i個字元）前有多少個相同的字元（下面講述求法），另一個就是在kmp函數中找出那個位置的下标；

其實還有一種就是暴力求出下标的方法，暴力法求解由于對時間度要求很高是以，在題目要求子串，和母串長度很大時此方法明顯就不适合了

AC如下 ：

int Violentsearch(char* s, char* p)
 {
 	int sLen = strlen(s);
 	int pLen = strlen(p);

 	int i = 0;
 	int j = 0;
 	while (i < sLen && j < pLen)
 	{
 		if (s[i] == p[j])
 		{
 			//如果目前字元比對成功（即S[i] == P[j]），則i++，j++    
 			i++;
 			j++;
 		}
 		else
 		{
 			//如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0    
 			i = i - j + 1;
 			//如果失配，每一次都要從上一次母串最開始周遊的下一個字元開始重新周遊
 			//例如母串是aabcy子串是abcy周遊到第二個失配那麼第二次就母串應該從第
 			//二個字元a開始重新周遊
 			j = 0;
 		}
 	}
 	//比對成功，傳回模式串p在文本串s中的位置，否則傳回-1
 	if (j == pLen)
 		return i - j;
 	else
 		return -1;}
           

kmp數組next求法：

next數組的作用就是在kmp函數中子串和母串比較時不相等的話把子串前移到子串前面一部分和母串有相同的的地方例如

對于子串p：a b c d a b c y

對應的next數組應該是 0 0 0 0 1 2 3 0

初始化時數組全為零

定義一個i=1; j=0; j在a的位置，i在b的位置，不相等是以i++;j還不動，直到i在第五個字元a的時候出現第一個相等的此時i++;j++;next[i]=j;後面的同樣相等直到遇到y的時候此時j在d上不相等是以j=next[j-1]（j前面又沒有相等的字首和字尾）

建議使用第二種第一種容易出現錯誤

第一種：

void get_next()
{
	int i = 1, j = 0;
	while(i < lenb)
	{
		if(j == 0 && b[i] != b[j])
		{
			i ++;
			next[i] = 0;
		}
		else if(j > 0 && b[i] != b[j])
			j = next[j-1];
		else
		{
			next[i] = j+1;
			i ++;
			j ++;
		}
	}
}
           

第二種

void Get_next()
 {
 	int i=1,j=0;
 	next[0]=-1;
 	while(i<m)
 	{
 		if(j==-1||p[i]==p[j])
 		{
 			j++;
 			i++;
 			next[i]=j;//目前i的位置有j個相等的字元
 		}
 		else
 		{
 			j=next[j];//縮小字首
 		}
 	}
 }
           

對于kmp函數：

先看看代碼吧

{
      Get_next();
  	int i=0,j=0;
  	while(i<n)
  	{
  	//要是子串和母串相同繼續往後進行比較
  		if(j==-1||s[i]==p[j])
  		{
  			i++;
  			j++;   
  		}
  		else//不相等就把子串往後移到子串前面的幾個字元和目前母串前幾個相同的地方
  		      //也就是上面的兩張圖檔
  		{
  			j=next[j];
  		}
  		
  	}
  	if(i==m)
  	return i-j;
  	else
  	return -1;
  }