理解KMP顽照，我們先簡單看一下這個過程再层。

對于abx--aby--這個匹配串呐粘，如果我們能夠順利匹配完y之前的字母囚灼，一個一個往后移動是意義不大的丹禀，最好的情況就是直接把第一個abx后移到aby匹配的位置放闺，看一下x能否匹配上拜英，如果匹配上了魁淳，就繼續(xù)向后嘗試匹配壕探；如果沒匹配上冈钦，說明這個abx也沒用，可以直接將a移動到x后面一個字母上嘗試匹配李请。

兩個相同子串a(chǎn)b移動的過程瞧筛，就需要要預處理，即next數(shù)組导盅，在說next數(shù)組之前较幌，我們先來引入兩個概念，理解這兩個概念白翻，是理解KMP的關鍵乍炉！

前綴就是以某一個字母開頭的所有字母集合绢片；后綴就是以某一個字母結尾的所有字母集合。

仍然以abx--aby--的匹配串作為例子岛琼，對于aby--中的b來說底循，b有一個后綴ab，對于abx--來說槐瑞，a有一個前綴ab熙涤，此時這兩個前后綴子串剛好相等。也就是說困檩，當我們在匹配過程中灭袁，假設文本串為--abx--abz--，指針在比較 y窗看！=z ，next數(shù)組讓指向y的指針改指向x倦炒，若x显沈！=z，那么直接重新匹配（此時后移了很多）逢唤；若x==z拉讯，那么指針后移繼續(xù)嘗試匹配。

再次強調(diào)一下鳖藕，在KMP中運用的前綴一定是以匹配串第一個字母開頭的前綴（這樣才能移動ＤЭ丁），后綴一定是指以當前這個字母之前的一個字母作為結尾的后綴（這樣在匹配到不相同的時候才好確認之前的字母是相同的）著恩。

如果
原始的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];  
        }  
    }  
}  

研究一下代碼是怎么操作的，看起來很簡單喉誊，理解起來還是有幾分復雜邀摆。

最重要的在注釋中寫了。既然j和k代表不同含義伍茄，我們看一下它的初值情況栋盹，本身就是不同步的，（k==-1會直接進入）相當于k是指向第一個元素敷矫，j是指向第二個元素例获。

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

我們注意到k++的情況，只有在p[k]==p[j]的時候啼器，極端情況旬渠，他們一直相等，此時k是從0（其實應該說-1）開始的端壳，一直加的過程中告丢，都保證了與p[j]的相同，就相當于k有多長（前綴）损谦，j也同時加了多長（后綴）岖免，所以對每一個j的next都標注一下此時與k這么長的前綴是相等的。

再說一個if里面的點照捡，就是j始終要比k大颅湘，同時還要next[j]=k，所以表達的含義是【以字母前一個字母作為后綴能達到的最長】

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

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