最近溫習了一下KMP算法。現在談談我對KMP算法的了解。
KMP算法目的：盡量快的解決單字元串比對的問題。
一、問題：
主字元串： ababcababababcab
模式串： abababab
判斷在主串中是否存在模式串，如果存在，在哪個位置。
二、解決
解決辦法很多，單談KMP算法的next擷取方法。
next數組的目标：在比對失敗的時候，将模式串的下标位置盡量的少的前移，使比對速度最快。
進一步說就是：在模式串的每一個位置進行切割（不包括目前位置），前面一段字元串中，找出一個字尾（即不包括第一個字元），使得完全比對自身的字首。
可能有點繞口，看圖！
1. 為了更直覺起見，我将模式串進行放大并影分身！你看到的是兩個模式串，但其實是一個（後面不再提醒）。
2. 那，這樣我們得到一段字元串aba，它隻存在一個字尾a，與其本身的字首a比對。如下圖。
3. 則，這個位置的next值就為1。即next[3]=1;如下圖。
4. 同理，如果我們在5位置切割，如下圖，得到next[5] = 3;如下圖。
5. 依次類推，所有的位置next值都可以得到，如下圖。
那麼next值是什麼，就是在目前位置比對失敗的時候，下标應該改變到的位置，繼續進行比對。
三、程式設計
1. 在程式設計的時候，很多地方都會把next的第一個位置設定為-1。即表示主串下标後移一位，重新開始比對模式串。
其實根據目前下标為0，且比對失敗這種情況，将主串下标後移也是可行的，不過書寫起來比較麻煩而已。
注意：可能你會注意到，在沒有優化的KMP算法中，總是有next[0] = -1; next[1] = 0;
原因是什麼？看前面二中的圖部分。多想想就知道了！
next擷取的c代碼，來源： http://blog.csdn.net/sowhat_ah/article/details/42168727
int get_next(const char *pstr, int *next)
{
int i = 0;
int k = -1;
int plen = strlen(pstr);
int mlen = plen - 1;
next[i] = k;
while(i < mlen)
{
if((-1 == k) || (pstr[i] == pstr[k]))
{
next[++ i] = ++ k;
}
else
{
k = next[k];
}
}
return plen;
}
2. 關于KMP的優化。就是優化next數組。
優化的原因：
a. 首先應該了解，next值的意思是将模式串的下标移到該位置，再與主串進行比較。
b. 那你想啊，如果模式串下标移動之後的位置，和目前下标指的字元是同一個字元，那麼比對肯定還是失敗的。還要繼續前移！
例如在位置4處比對失敗，根據next[4]=2;跳轉!
比對之後跳轉到位置2的時候，還是a！！！肯定比對不成功了！是以還要繼續往前跳！！！如下圖。
如果在建立next的時候，提前把這個“我再跳”的操作已經做好，一步跳到最前面！豈不是更好！！！如下圖：
了解到這裡，其實可以把next數組分兩步走，
第1步：按照扇面1中的代碼，建立next數組。
第2步：周遊next數組，如果跳轉到的位置和目前的位置是相同的字元，則把目前的next值賦為跳轉到的位置的next值。如下圖。
（隻周遊到3的位置，後面依次類推。）
最終得到的next如下圖，陰影部分均為第2步的所述的原因。
最後奉上優化的代碼（将第1步和第2步合并）。
//zh for zhuhong
int get_next_zh(const char *pstr, int *next)
{
int i = 0;
int k = -1;
int plen = strlen(pstr);
int mlen = plen - 1;
next[i] = k;
while(i < mlen)
{
if((-1 == k) || (pstr[i] == pstr[k]))
{
next[++ i] = ++ k;
// here is the modification
if(pstr[i] == pstr[k])
{
next[i] = next[k];
}
// end the modification
}
else
{
k = next[k];
}
}
return plen;
}