以前看到資料結構中字元串的模式比對時，花了半天的時間，才把KMP算法中的next函數整明白了，結果過了幾天在看到這時，隻記得next[j+1]=next[j]+1，但是有時候能套公式正确算出，有時候就算不對，是以今天再從新理一遍思路，順便記錄下來，防止哪天腦子再短路了，又不知道怎麼求解的了。算法
先看看next資料值的求解方法
位序 1 2 3 4 5 6 7 8 9
模式串 a b a a b c a b c
next值 0 1 1 2 2 3 1 2 3
next數組的求解方法是：
1.第一位的next值為0
2.第二位的next值為1
後面求解每一位的next值時，根據前一位進行比較
3.第三位的next值：第二位的模式串為b ,對應的next值為1;将第二位的模式串b與第一位的模式串a進行比較，不相等；則第三位的next值為1(其餘狀況均為1)
4.第四位的next值：第三位的模式串為a ,對應的next值為1;将第三位的模式串a與第一位的模式串a進行比較，相同，則第四位的next值得為1+1=2
5.第五位的next值：第四位的模式串為a，對應的next值為2;将第四位的模式串a與第二位的模式串b進行比較，不相等；第二位的b對應的next值為1,則将第四位的模式串a與第一位的模式串a進行比較，相同，則第五位的next的值為1+1=2
6.第六位的next值：第五位的模式串為b，對應的next值為2;将第五位的模式串b與第二位的模式中b進行比較，相同，則第六位的next值為2+1=3
7.第七位的next值：第六位的模式串為c，對應的next值為3;将第六位的模式串c與第三位的模式串a進行比較，不相等；第三位的a對應的next值為1，
則将第六位的模式串c與第一位的模式串a進行比較，不相同，則第七位的next值為1(其餘狀況)
8.第八位的next值：第七位的模式串為a，對應的next值為1;将第七位的模式串a與第一位的模式串a進行比較，相同，則第八位的next值為1+1=2
9.第八位的next值：第八位的模式串為b，對應的next值為2;将第八位的模式串b與第二位的模式串b進行比較，相同，則第九位的next值為2+1=3
若是位數更多，依次類推
KMP算法的關鍵在于求算next[]數組的值，即求算模式串每一個位置處的最長字尾與字首相同的長度，下面按照遞推的思想總結一下求解next[]數組：
根據定義next[1]=0，假設next[j]=k, 即P[1...k-1]==P[j-k,j-1]數組
1)若P[j]==P[k]，則有P[1..k]==P[j-k,j]，很顯然，若是next[j]=k; 則next[j+1]=next[j]+1=k+1;不然next[j+1]=k+1!=next[j]+1;(當初就想着記公式簡單能夠直接套用呢，結果隻記住next[j+1]=next[j]+1以緻于後來迷糊了)
2)若P[j]!=P[k]，則能夠把其看作模式比對的問題，即比對失敗的時候，k值如何移動，顯然k=next[k]。
是以能夠這樣去實作：資料結構
void getNext(char *p,int *next)
{
int j,k;
next[1]=0;
j=1;
k=0;
while(j
{
if(k==0||p[j]==p[k]) //比對的狀況下,p[j]==p[k]，next[j+1]=k+1;
{
j++;
k++;
next[j]=k;
}
else //p[j]!=p[k]，k=next[k]
k=next[k];
}
}
KMP模式比對算法改進：函數
後來有人發現其實KMP算法仍是有缺陷的，好比主串S=“aaaabcde”，子串T=“aaaaag”，其next數組為012345；當i=5 ，j=5是“b”與“a”不比對，此時j=next[5]=4，又發現j=4時，“b”與“a”不比對，依次類推，直到j=next[1]=0;此時i++，j++，i=6，j=1進而咱們發現中間有多餘的判斷，因為子串T中第二、三、四、5位置的字元都與首位的“a”相同，便可以用首位next[1]的值去取代與它字元相等的後續next[j]的值，即next數組改成000005，此時由i=5，j=5時“b”與“a”不比對，此時j=next[5]=0；此時i++，j++獲得i=6，j=1，便可省去中間的多餘判斷。是以咱們須要改進next函數的求解方法。spa
void get_nextval(String T, int *nextval)
{
int i,j;
i=1;
j=0;
nextval[1]=0;
while (i
{
if(j==0 || T[i]== T[j])
{
++i;
++j;
if (T[i]!=T[j])
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else
j= nextval[j];
}
}