看數(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í)候直接來簡書看,方便芦昔。