考研復習過程中，看到王道的《數據結構》中對KMP的解釋有感而發(fā)。感覺王道解釋的有點復雜，然后自己理解了一下，在此寫一點心得

如果我記得沒錯，next數組的獲得的代碼是長這個樣子的。

void getNext(char *s, int *next) {
    next[1] = 0;
    int i = 1;
    int j = 0;
    while (i < s[0]) {
        if (j == 0 || s[i] == s[j]) {
            ++j; ++i; next[i] = j;
        } else
            j = next[j];
    }
}

接下來把王道《數據結構》中的解釋放出來

王道《數據結構》中對KMP的解釋

大家可以嘗試著理解一下，如果覺得這么解釋更容易理解就可以不往下看了..

接下來就是我對next數組產生從不同角度的理解

先隨便寫一個字符串：abcc acab cc
根據專科班應有的素質，應該能得出next數組內容為0111 1212 34

步驟為：

next[0]不存在，next[1]必定等于0（規(guī)定的）

如何求得next[3]？
若按照王道《數據結構》中的步驟，很難操作，并且與代碼所呈現的邏輯不符，反正我理解起來很別扭。
但仔細看代碼，其實很容易就發(fā)現next[3]的值就是若next[2]==next[1]則next[3] = next[2] + 1。否則，就和string[1]的next值即next[1]值索引的string字符做比較。

此時next[1] = 0，而規(guī)則就是若比到next值出現0時，直接得出下一個next值為1，或者說同時令index和next[index]加1（next是根據當前所在的值，此時next = 0）

于是就得出next[3]=1。

接下來同樣讓string[3]與string[next[3]]（即string[1]）相比，不等，next為0，加一。。。

同理，注意next[5]的1是根據string[4]與string[next[4]]（即string[1]）相比較得出的

然后string[5]與string[next[5]]（即string[1]）相比，相等，于是index++，next[index]=next[index-1]+1 （就是加了一）

然后理所應當的string[6]與string[next[6]]（即string[2]）相比，不一樣，轉而string[6]與string[next[next[6]]]（即string[1]），又不同，而此時next [next[next[6]]] == 0，于是next[++index] = next[next[next[6]]] + 1

。。。
。。。
。。。