KMPアルゴリズムのnext配列は最も簡単で乱暴な掌握です.

「KKKPアルゴリズム」とも呼ばれていますが、このアルゴリズムの導入は文字列整合の整合効率を大きく最適化しました.非常に有名なアルゴリズムです.その原理は合致する文字列にnext配列を加えることによって、この配列をそのトレースガイドとして、不必要なトレースを減算することです.まず、next配列の規則を見てみます.簡単にまとめますと、現在位置の接頭辞のマッチングがあるかどうかを判断します.もしあれば、接尾文字列の長さをnとしたら、現在位置でn＋1を記入します.簡単な例を挙げて、文字列Tとそのnext配列.

T          a b a a b a a b
next       0 1 1 2 2 3 4 2

最初にプレフィックスを明確にするには、最初のビットから固定されていなければならず、2番目のビットから開始することはできません.私たちは最初の分析を行います.next[1]は常に0です.これは解釈しません.そして、第二位からもきっと1です.そして、私たちは3位から見ます.この時、プレフィックスの値はaで、接頭辞はbで、1ではなく、4位で、プレフィックスは相変わらずaで、接頭辞はaであります.5位、接尾辞はa aがありますが、接頭辞のマッチングがありませんので、接尾辞aとaが一致するだけで、2を記入します.第6位、プレフィクスはabでも良いし、サフィックスはabでもあり、マッチング、長さは2、2＋1である.7番目のビット、拡張子abaは、3であり、3＋1であるマッチするプレフィックス値を見つけることができる.これは比較的に簡単な理解で、もしあなたは試験に対処するのだならば、問題をしてここを見て終わってもいいです.コードの一部を見てきましたが、コードに沿ってシングルステップで調整して理解できます.

void get_next(String T, int *next)
{
	int i = 1;
	int j = 0;
	next[1] = 0;
	while (i < T[0])
	{
		if (0==j || T[i] == T[j])//       ，   next[]  ；
		{
			i++;
			j++; 
			if (T[i] != T[j]) 
			{ next[i] = j; }//      next[i];
			else
				next[i] = next[j];
		}
		else {
			j = next[j];//   ，
		}
	}
}