問題描述
輸入：一個文本串S，和一個模式串P
輸出：若幹行，每行包含一個整數，表示s2在s1中出現的位置
在一個母字元串S（文本串）中查找一個子字元串P（模式串）有很多方法。Knuth-Morris-Pratt 字元串查找算法(簡稱“KMP”)是一種最常見的改進算法，由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年聯合發表，故取這3人的姓氏命名此算法。
這個算法針對的是子串有對稱屬性，如果有對稱屬性，那麼就需要向前查找是否有可以再次比對的内容。
注意：這裡的對稱性，不是中心對稱，而是中心字元塊對稱，比如不是abccba，而是abcabc這種對稱。
KMP
一般最粗暴的方法，就是比對失敗後，一個字元一個字元往後挪來進行比較，比如：
KMP可以在比對過程中失配的情況下，有效地多往後面跳幾個字元，加快比對速度。
下面先直接給出KMP的算法流程：
圖一(a)
圖一(b)
圖二(a)
圖二(b)
假設現在文本串S比對到
i
位置，模式串P比對到
j
位置
- 目前字元比對成功（即
S[i] == P[j]
k++
j++
- 目前字元比對失敗（即
S[i] != P[j]
j = next[j]
j - next [j]
換言之，當比對失敗時，模式串向右移動的位數為：失配字元所在位置 - 失配字元對應的next 值（next 數組的求解會在下文詳細闡述），即移動的實際位數為：
j - next[j]
，且此值≥1。
next數組（字首數組）
每一個模式串P都有有一個固定的next數組，它記錄着字元串比對過程中失配情況下可以向前多跳幾個字元，當然它描述的也是子串的對稱程度，程度越高，值越大，當然之前可能出現再比對的機會就更大。
這個next數組的求法是KMP算法的關鍵，看到别的地方到處是數學公式推導，我這裡用圖示的方法友善大家了解。
- 紅色：模式串P目前已經比對好的相同前字尾
- 藍色：模式串P目前比對的位置，就是
j
- 橙色：模式串P目前比對的最長字首的後一位，即為
k
如果
p[j] == p[k]
，則皆大歡喜，
next[j] = next[j - 1] + 1
p[j] != p[k]
，隻能尋找更短的相同前字尾比對，我們看下圖
- 灰色：目前已經比對好相同前字尾中的最長公共前字尾
- 紫色：目前已經比對好相同前字尾中的字首的後一位
因為紅色部分是已經比對好的，是以既然第二個的後面為灰色部分，第一個的前面和後面也為灰色部分，接下來對應的，第二個前面的也為灰色部分。
查閱
藍色
與
紫色
是否比對。
此時，又回到最初的那一步（遞歸），求解某個位置的next值是一個循環過程，不斷檢查 上一位的最長字首的後一位.
如果相等
next[j] = next[k] + 1
，否則
k = next[k]
代碼
//優化過後的next 數組求法
void GetNextval(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[j] == p[k]){
++j;
++k;
//較之前next數組求法，改動在下面4行
if (p[j] != p[k])
next[j] = k; //之前隻有這一行
else
//因為不能出現p[j] = p[ next[j ]]，是以當出現時需要繼續遞歸，k = next[k] = next[next[k]]
next[j] = next[k];
}
else{
k = next[k];
}
}
}