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