看數(shù)據(jù)結構的書，字符串章節(jié)提到這個字符串匹配的算法。結果一看，真是比較難理解，不愧是三個人想出來的算法，以三個人的名字命名這個算法KMP。書上講的也是看不明白，只能上網(wǎng)搜搜比較通俗易懂的回答 。結果大部分都是復制粘貼，提到遞歸什么的，越看越糊涂，估計作者自己都不明白。后來還是在知乎上看到一個點贊數(shù)比較多的，結果一看，講的不錯。知乎不愧是程序員用戶比較多的平臺，大神就是吊。
自己看了看，想了想，動手抄一遍，運行一下，加深記憶理解。
原文地址： 鏈接
直接開始廢話，也都是抄這位作者的，只是為了自己寫一遍
一、問題：定位出一個字符串在另一個字符串中完全匹配的位置。
比如目標字符串：abcabcdee 主字符串：xyzabcabcdeezzz
明顯一看，結果就是3。在第3位置的a開始匹配到最后。
如果用樸素方法，直接遍歷，兩個字符串挨個對比，如果不匹配，目標字符串從頭開開始，主字符串回到上次匹配位置的下一個位置。每次不匹配的時候，都需要從頭開始。最差情況下，主字符串從頭到最后，目標字符串每次都是到最后一個字符不匹配，所以時間復雜度就是O（m*n）。
二、樸素方法的弊端
樸素方法每次匹配失敗的時候都要從頭開始，比如匹配到第6個字符失敗了，如果知道了失敗了的位置之前到字符串，也就是前5個字符的前綴和后綴的交集，就可以從這個交集長度的位置開始下次匹配了，這樣，目標字符串不用從0開始，主字符串也不用回溯到上一次開始的地方了。就節(jié)省了很多步。
三、字符串前綴和后綴的交集
前綴：一個字符串的子字符串，確保包含第一個字符，但不包含自身。
后綴：一個字符串的子字符串，確保包含最后一個字符，但不包含自身。
比如：abab
前綴集合：a、ab、aba。后綴集合：b、ab、bab。
所以集合的交集是ab。交集可能不止一個。需要的是最大長度。
有了前后綴交集的長度，說明可以重疊著么長，既然都重疊了，說明前面重疊部分不需要對比了，直接從重疊的下一個位置開始就行了。
KMP的關鍵就是求目標字符串每個位置的前后綴交集里最大長度。
四、部分匹配表
比如：字符串“abababca”
首先，對于這個數(shù)組，最后一個位置的值是用不上的。因為這個表的用處是在匹配失敗的時候需要回溯，回溯位置是前面子字符串的表值+1。
比如目標這個字符串長度是8，匹配到位置6失敗了，這時候需要回溯到前5個子字符串，第5位置的值是2，這時候需要回溯到3。從3位置的字符開始接著匹配。
媽的，亂七八糟，說不清。
所以真正用到的值是當前位置前一個位置的表值，最有一個位置的值只能在全部匹配完的時候才用到，但是全部匹配完意味著匹配成功，找到結果了，更用不上它了。所以最后一個值沒什么卵用。
而且為了編程方便，就把每個位置對應的值往后推了一格，把最后一個扔了，反正也用不上，第一個空了出來，用-1代替。所以一般叫next數(shù)組。匹配失敗的時候，回溯位置也不用上一個位置的值+1了，直接就是自己位置對應的值了。
void getNext(char *p, int *arr) {
int i = 0;
int j = -1;
arr[0] = -1;
while (i < strlen(p)-1) {
if (j == -1 || p[i] == p[j]) {
I++;
j++;
arr[i] = j;
}else{
j = arr[j];
}
}
}
跟著流程走一下，可以發(fā)現(xiàn)，這個匹配表的前兩位固定是-1、0
i的位置表示自己的后綴字符串，j表示前綴字符串。
這里比較繞，說不清，真雞兒難。該睡覺了。
KMP
int kmpMethod(char *str, char *target, int *next) {
int i = 0;
int j = 0;
while (i < strlen(str) && j < (int)strlen(target)) {
if (j == -1 || str[i] == target[j]) {
I++;
j++;
}else{
j = next[j];
}
}
if (j == strlen(target)) {
return i - j;
}
return -1;
}
匹配成功，各自往后走，各個位置+1。
如果匹配失敗，就找當前位置的前面子字符串的匹配表的值，意味找最大重合部分，如果有重合部分，就不用比較前面的了，直接從重合部分開始比較后面的。如果當前位置前面子字符串值是0，意味著沒有重合部分，就縮小范圍，尋找上一個子字符串的前后綴重合部分，有的話就開始匹配，沒有的話，就接著尋找上上一個，直到值是-1，意味著當前位置前面的子字符串沒有一個完全沒有重疊的部分，就只能從頭開始，就各自+1，目標字符串從頭開始了，回溯到0，主字符串是一直往后走的，不回溯。
注：strlen得到無符號整型，j的值是-1的時候，會出現(xiàn)-1>無符號數(shù)值的問題，所以需要用int強轉(zhuǎn)一下。
說不明白，哈哈?？偟膩碚fKMP算法過程容易理解，求部分匹配表那個算法比較難理解。反正這陣子睡眠不好，剛好記錄一下。想看的時候直接來簡書看，方便。
