理解KMP，我們先簡單看一下這個(gè)過程。

對于abx--aby--這個(gè)匹配串，如果我們能夠順利匹配完y之前的字母，一個(gè)一個(gè)往后移動(dòng)是意義不大的，最好的情況就是直接把第一個(gè)abx后移到aby匹配的位置，看一下x能否匹配上，如果匹配上了，就繼續(xù)向后嘗試匹配；如果沒匹配上，說明這個(gè)abx也沒用，可以直接將a移動(dòng)到x后面一個(gè)字母上嘗試匹配。

兩個(gè)相同子串a(chǎn)b移動(dòng)的過程，就需要要預(yù)處理，即next數(shù)組，在說next數(shù)組之前，我們先來引入兩個(gè)概念，理解這兩個(gè)概念，是理解KMP的關(guān)鍵！

前綴就是以某一個(gè)字母開頭的所有字母集合；后綴就是以某一個(gè)字母結(jié)尾的所有字母集合。

仍然以abx--aby--的匹配串作為例子，對于aby--中的b來說，b有一個(gè)后綴ab，對于abx--來說，a有一個(gè)前綴ab，此時(shí)這兩個(gè)前后綴子串剛好相等。也就是說，當(dāng)我們在匹配過程中，假設(shè)文本串為--abx--abz--，指針在比較 y！=z ，next數(shù)組讓指向y的指針改指向x，若x！=z，那么直接重新匹配（此時(shí)后移了很多）；若x==z，那么指針后移繼續(xù)嘗試匹配。

再次強(qiáng)調(diào)一下，在KMP中運(yùn)用的前綴一定是以匹配串第一個(gè)字母開頭的前綴（這樣才能移動(dòng)！），后綴一定是指以當(dāng)前這個(gè)字母之前的一個(gè)字母作為結(jié)尾的后綴（這樣在匹配到不相同的時(shí)候才好確認(rèn)之前的字母是相同的）。

如果
原始的next數(shù)組：

void Next(char* p,int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前綴，p[j]表示后綴  
        if (k == -1 || p[k] == p[j])   
        {  
            ++k;  
            ++j;  
            next[j] = k;  
        }  
        else   
        {  
            k = next[k];  
        }  
    }  
}  

研究一下代碼是怎么操作的，看起來很簡單，理解起來還是有幾分復(fù)雜。

最重要的在注釋中寫了。既然j和k代表不同含義，我們看一下它的初值情況，本身就是不同步的，（k==-1會直接進(jìn)入）相當(dāng)于k是指向第一個(gè)元素，j是指向第二個(gè)元素。

繼續(xù)研究j和k，我們發(fā)現(xiàn)，j只有第一個(gè)if是有變化的，而且只有++，所以是硬加的，相當(dāng)于遍歷整個(gè)匹配串，給匹配串上面標(biāo)注0.1.2.3...的下標(biāo)。

我們注意到k++的情況，只有在p[k]==p[j]的時(shí)候，極端情況，他們一直相等，此時(shí)k是從0（其實(shí)應(yīng)該說-1）開始的，一直加的過程中，都保證了與p[j]的相同，就相當(dāng)于k有多長（前綴），j也同時(shí)加了多長（后綴），所以對每一個(gè)j的next都標(biāo)注一下此時(shí)與k這么長的前綴是相等的。

再說一個(gè)if里面的點(diǎn)，就是j始終要比k大，同時(shí)還要next[j]=k，所以表達(dá)的含義是【以字母前一個(gè)字母作為后綴能達(dá)到的最長】

至于else里面的內(nèi)容，暫時(shí)我只能膚淺得認(rèn)為，以abx--aby--做例子，當(dāng)j指向b的時(shí)候，先進(jìn)if，使得y對應(yīng)的next已經(jīng)記錄了2，然后再次循環(huán)，j不變，進(jìn)入else語句，next[2]明顯是等于0的，所以相當(dāng)于把k的數(shù)字調(diào)整到上一次達(dá)到的狀態(tài)，這個(gè)next數(shù)組涉及了有限自動(dòng)機(jī)，等后面好好看一下再聊吧。

認(rèn)真看看這個(gè)再來談吧從頭到尾徹底理解KMP-Chris_z)