KMP

看數(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”


匹配數(shù)組.jpg

首先褥伴,對于這個(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


尋找過程.jpg

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

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末诱贿,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子咕缎,更是在濱河造成了極大的恐慌珠十,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,807評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件凭豪,死亡現(xiàn)場離奇詭異焙蹭,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)墅诡,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門壳嚎,熙熙樓的掌柜王于貴愁眉苦臉地迎上來桐智,“玉大人末早,你說我怎么就攤上這事∷低ィ” “怎么了然磷?”我有些...
    開封第一講書人閱讀 169,589評(píng)論 0 363
  • 文/不壞的土叔 我叫張陵,是天一觀的道長刊驴。 經(jīng)常有香客問我姿搜,道長,這世上最難降的妖魔是什么捆憎? 我笑而不...
    開封第一講書人閱讀 60,188評(píng)論 1 300
  • 正文 為了忘掉前任舅柜,我火速辦了婚禮,結(jié)果婚禮上躲惰,老公的妹妹穿的比我還像新娘致份。我一直安慰自己,他們只是感情好础拨,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,185評(píng)論 6 398
  • 文/花漫 我一把揭開白布氮块。 她就那樣靜靜地躺著,像睡著了一般诡宗。 火紅的嫁衣襯著肌膚如雪滔蝉。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,785評(píng)論 1 314
  • 那天塔沃,我揣著相機(jī)與錄音蝠引,去河邊找鬼。 笑死,一個(gè)胖子當(dāng)著我的面吹牛螃概,可吹牛的內(nèi)容都是我干的边坤。 我是一名探鬼主播,決...
    沈念sama閱讀 41,220評(píng)論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼谅年,長吁一口氣:“原來是場噩夢啊……” “哼茧痒!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起融蹂,我...
    開封第一講書人閱讀 40,167評(píng)論 0 277
  • 序言:老撾萬榮一對情侶失蹤旺订,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后超燃,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體区拳,經(jīng)...
    沈念sama閱讀 46,698評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,767評(píng)論 3 343
  • 正文 我和宋清朗相戀三年意乓,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了樱调。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,912評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡届良,死狀恐怖笆凌,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情士葫,我是刑警寧澤乞而,帶...
    沈念sama閱讀 36,572評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站慢显,受9級(jí)特大地震影響爪模,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜荚藻,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,254評(píng)論 3 336
  • 文/蒙蒙 一屋灌、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧应狱,春花似錦共郭、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至罐韩,卻和暖如春憾赁,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背散吵。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評(píng)論 1 274
  • 我被黑心中介騙來泰國打工龙考, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留蟆肆,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,359評(píng)論 3 379
  • 正文 我出身青樓晦款,卻偏偏與公主長得像炎功,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子缓溅,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,922評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 字符串匹配KMP算法詳解 1. 引言 以前看過很多次KMP算法蛇损,一直覺得很有用,但都沒有搞明白坛怪,一方面是網(wǎng)上很少有...
    張晨輝Allen閱讀 2,412評(píng)論 0 3
  • 數(shù)據(jù)結(jié)構(gòu)與算法--KMP算法查找子字符串 部分內(nèi)容和圖片來自這三篇文章: 這篇文章淤齐、這篇文章、還有這篇他們寫得非常...
    sunhaiyu閱讀 1,743評(píng)論 1 21
  • title: 串的模式匹配算法之kmptags: 數(shù)據(jù)結(jié)構(gòu)與算法之美author: 辰砂tj 1.引言 首先我們需...
    tojian閱讀 975評(píng)論 0 0
  • KMP的由來 在KMP算法之前,對文本進(jìn)行匹配時(shí)使用的是樸素模式匹配算法,也就是最簡單匹配算法.當(dāng)然運(yùn)行效率也是讓...
    圣光懺悔閱讀 1,764評(píng)論 2 13
  • 參考文章 知乎:如何更好的理解和掌握 KMP 算法?從頭到尾徹底理解KMPKMP 算法(1):如何理解 KMP(原...
    Mjolnir1107閱讀 992評(píng)論 0 0