任何一個演算法的理解首先得明白演算法本身解決什麼問題。

KMP演算法基本上用來解決字串的匹配問題，比如一個字串是否包含另一個字串，所以這個演算法的關鍵是利用匹配失敗後的資訊，儘量減少模式串與主串的匹配次數以達到快速匹配的目的。其中最重要的便是求next函式，函式包含了模式串的區域性匹配資訊。

下面我們用一個例子來具體講解如何求next陣列：

1.第一位的next值為0 ;

2.第二位的next值為1 後面求解每一位的next值時，根據前一位進行比較;

3.第三位的next值：第二位的模式串為b ,對應的next值為1;將第二位的模式串b與第一位的模式串a進行比較，不相等；則第三位的next值為1;

4.第四位的next值：第三位的模式串為a ,對應的next值為1;將第三位的模式串a與第一位的模式串a進行比較，相同，則第四位的next值得為2;

5.第五位的next值：第四位的模式串為a，對應的next值為2;將第四位的模式串a與第二位的模式串b進行比較，不相等；第二位的b對應的next值為1,則將第四位的模式串a與第一位的模式串a進行比較，相同，則第五位的next的值為2;

6.第六位的next值：第五位的模式串為b，對應的next值為2;將第五位的模式串b與第二位的模式中b進行比較，相同，則第六位的next值為3 ;

7.第七位的next值：第六位的模式串為c，對應的next值為3;將第六位的模式串c與第三位的模式串a進行比較，不相等；第三位的a對應的next值為1，則將第六位的模式串c與第一位的模式串a進行比較，不相同，則第七位的next值為1;

8.第八位的next值：第七位的模式串為a，對應的next值為1;將第七位的模式串a與第一位的模式串a進行比較，相同，則第八位的next值為2 ;

https://blog.csdn.net/u013486414

PS：下面附一段求next的程式碼供參考：

int get_next( )

{

int i=0,j=-1;

next[0]=-1;

while(i<n)

{

if(j==-1||c[i]==c[j])

{

++i;

++j;

next[i]=j;

}

else

j=next[j];

}

}