看數(shù)據(jù)結(jié)構(gòu)的書口糕，字符串章節(jié)提到這個(gè)字符串匹配的算法。結(jié)果一看磕蛇，真是比較難理解景描，不愧是三個(gè)人想出來的算法，以三個(gè)人的名字命名這個(gè)算法KMP秀撇。書上講的也是看不明白超棺，只能上網(wǎng)搜搜比較通俗易懂的回答 。結(jié)果大部分都是復(fù)制粘貼呵燕，提到遞歸什么的棠绘，越看越糊涂，估計(jì)作者自己都不明白再扭。后來還是在知乎上看到一個(gè)點(diǎn)贊數(shù)比較多的氧苍，結(jié)果一看，講的不錯(cuò)泛范。知乎不愧是程序員用戶比較多的平臺(tái)候引，大神就是吊。
自己看了看敦跌，想了想澄干，動(dòng)手抄一遍，運(yùn)行一下柠傍，加深記憶理解麸俘。
原文地址： 鏈接
直接開始廢話，也都是抄這位作者的惧笛，只是為了自己寫一遍
一从媚、問題：定位出一個(gè)字符串在另一個(gè)字符串中完全匹配的位置。
比如目標(biāo)字符串：abcabcdee 主字符串：xyzabcabcdeezzz
明顯一看患整，結(jié)果就是3拜效。在第3位置的a開始匹配到最后喷众。
如果用樸素方法，直接遍歷紧憾，兩個(gè)字符串挨個(gè)對比到千，如果不匹配，目標(biāo)字符串從頭開開始赴穗，主字符串回到上次匹配位置的下一個(gè)位置憔四。每次不匹配的時(shí)候，都需要從頭開始般眉。最差情況下了赵，主字符串從頭到最后，目標(biāo)字符串每次都是到最后一個(gè)字符不匹配甸赃，所以時(shí)間復(fù)雜度就是O（m*n）柿汛。
二、樸素方法的弊端
樸素方法每次匹配失敗的時(shí)候都要從頭開始埠对，比如匹配到第6個(gè)字符失敗了苛茂，如果知道了失敗了的位置之前到字符串，也就是前5個(gè)字符的前綴和后綴的交集鸠窗，就可以從這個(gè)交集長度的位置開始下次匹配了妓羊，這樣，目標(biāo)字符串不用從0開始稍计，主字符串也不用回溯到上一次開始的地方了躁绸。就節(jié)省了很多步。
三臣嚣、字符串前綴和后綴的交集
前綴：一個(gè)字符串的子字符串净刮，確保包含第一個(gè)字符，但不包含自身硅则。
后綴：一個(gè)字符串的子字符串淹父，確保包含最后一個(gè)字符，但不包含自身怎虫。
比如：abab
前綴集合：a暑认、ab、aba大审。后綴集合：b蘸际、ab、bab徒扶。
所以集合的交集是ab粮彤。交集可能不止一個(gè)。需要的是最大長度。
有了前后綴交集的長度导坟，說明可以重疊著么長屿良，既然都重疊了，說明前面重疊部分不需要對比了惫周，直接從重疊的下一個(gè)位置開始就行了尘惧。
KMP的關(guān)鍵就是求目標(biāo)字符串每個(gè)位置的前后綴交集里最大長度。
四闯两、部分匹配表
比如：字符串“abababca”
首先褥伴，對于這個(gè)數(shù)組谅将，最后一個(gè)位置的值是用不上的漾狼。因?yàn)檫@個(gè)表的用處是在匹配失敗的時(shí)候需要回溯，回溯位置是前面子字符串的表值+1饥臂。
比如目標(biāo)這個(gè)字符串長度是8逊躁，匹配到位置6失敗了，這時(shí)候需要回溯到前5個(gè)子字符串隅熙，第5位置的值是2稽煤，這時(shí)候需要回溯到3。從3位置的字符開始接著匹配囚戚。
媽的酵熙，亂七八糟，說不清驰坊。
所以真正用到的值是當(dāng)前位置前一個(gè)位置的表值匾二，最有一個(gè)位置的值只能在全部匹配完的時(shí)候才用到，但是全部匹配完意味著匹配成功拳芙，找到結(jié)果了察藐，更用不上它了。所以最后一個(gè)值沒什么卵用舟扎。
而且為了編程方便分飞，就把每個(gè)位置對應(yīng)的值往后推了一格，把最后一個(gè)扔了睹限，反正也用不上譬猫，第一個(gè)空了出來，用-1代替羡疗。所以一般叫next數(shù)組删窒。匹配失敗的時(shí)候，回溯位置也不用上一個(gè)位置的值+1了顺囊，直接就是自己位置對應(yīng)的值了肌索。
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)，這個(gè)匹配表的前兩位固定是-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;
}
匹配成功夷家，各自往后走，各個(gè)位置+1敏释。
如果匹配失敗库快，就找當(dāng)前位置的前面子字符串的匹配表的值，意味找最大重合部分钥顽，如果有重合部分义屏，就不用比較前面的了，直接從重合部分開始比較后面的蜂大。如果當(dāng)前位置前面子字符串值是0闽铐，意味著沒有重合部分，就縮小范圍奶浦，尋找上一個(gè)子字符串的前后綴重合部分兄墅，有的話就開始匹配，沒有的話澳叉，就接著尋找上上一個(gè)隙咸，直到值是-1，意味著當(dāng)前位置前面的子字符串沒有一個(gè)完全沒有重疊的部分耳高，就只能從頭開始扎瓶，就各自+1，目標(biāo)字符串從頭開始了泌枪，回溯到0概荷，主字符串是一直往后走的，不回溯碌燕。
注：strlen得到無符號(hào)整型误证，j的值是-1的時(shí)候，會(huì)出現(xiàn)-1>無符號(hào)數(shù)值的問題修壕，所以需要用int強(qiáng)轉(zhuǎn)一下愈捅。
說不明白，哈哈慈鸠±督鳎總的來說KMP算法過程容易理解，求部分匹配表那個(gè)算法比較難理解。反正這陣子睡眠不好譬巫，剛好記錄一下咖楣。想看的時(shí)候直接來簡書看，方便芦昔。
