字符串匹配的KMP算法

算法舉例來說绘闷,有一個字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一個字符串"ABCDABD"捐迫?

許多算法可以完成這個任務(wù),Knuth-Morris-Pratt算法(簡稱KMP)是最常用的之一爱葵。它以三個發(fā)明者命名施戴,起頭的那個K就是著名科學(xué)家Donald Knuth反浓。

這種算法不太容易理解,網(wǎng)上有很多解釋赞哗,但讀起來都很費(fèi)勁勾习。直到讀到Jake Boxer的文章,我才真正理解這種算法懈玻。下面,我用自己的語言乾颁,試圖寫一篇比較好懂的KMP算法解釋涂乌。

1.

首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一個字符與搜索詞"ABCDABD"的第一個字符英岭,進(jìn)行比較湾盒。因?yàn)锽與A不匹配,所以搜索詞后移一位诅妹。

2.

因?yàn)锽與A不匹配罚勾,搜索詞再往后移。

3.

就這樣吭狡,直到字符串有一個字符尖殃,與搜索詞的第一個字符相同為止。

4.

接著比較字符串和搜索詞的下一個字符划煮,還是相同送丰。

5.

直到字符串有一個字符,與搜索詞對應(yīng)的字符不相同為止弛秋。

6.

這時器躏,最自然的反應(yīng)是,將搜索詞整個后移一位蟹略,再從頭逐個比較登失。這樣做雖然可行,但是效率很差挖炬,因?yàn)槟阋?搜索位置"移到已經(jīng)比較過的位置揽浙,重比一遍。

7.

一個基本事實(shí)是茅茂,當(dāng)空格與D不匹配時捏萍,你其實(shí)知道前面六個字符是"ABCDAB"。KMP算法的想法是空闲,設(shè)法利用這個已知信息令杈,不要把"搜索位置"移回已經(jīng)比較過的位置,繼續(xù)把它向后移碴倾,這樣就提高了效率逗噩。

8.

怎么做到這一點(diǎn)呢掉丽?可以針對搜索詞,算出一張《部分匹配表》(Partial Match Table)异雁。這張表是如何產(chǎn)生的捶障,后面再介紹,這里只要會用就可以了纲刀。

9.

已知空格與D不匹配時项炼,前面六個字符"ABCDAB"是匹配的。查表可知示绊,最后一個匹配字符B對應(yīng)的"部分匹配值"為2锭部,因此按照下面的公式算出向后移動的位數(shù):

移動位數(shù) = 已匹配的字符數(shù) - 對應(yīng)的部分匹配值

因?yàn)?6 - 2 等于4,所以將搜索詞向后移動4位面褐。

10.

因?yàn)榭崭衽cC不匹配拌禾,搜索詞還要繼續(xù)往后移。這時展哭,已匹配的字符數(shù)為2("AB")湃窍,對應(yīng)的"部分匹配值"為0。所以匪傍,移動位數(shù) = 2 - 0您市,結(jié)果為 2,于是將搜索詞向后移2位析恢。

11.

因?yàn)榭崭衽cA不匹配墨坚,繼續(xù)后移一位。

12.

逐位比較映挂,直到發(fā)現(xiàn)C與D不匹配泽篮。于是,移動位數(shù) = 6 - 2柑船,繼續(xù)將搜索詞向后移動4位帽撑。

13.

逐位比較,直到搜索詞的最后一位鞍时,發(fā)現(xiàn)完全匹配亏拉,于是搜索完成。如果還要繼續(xù)搜索(即找出全部匹配)逆巍,移動位數(shù) = 7 - 0及塘,再將搜索詞向后移動7位,這里就不再重復(fù)了锐极。

14.

下面介紹《部分匹配表》是如何產(chǎn)生的笙僚。

首先,要了解兩個概念:"前綴"和"后綴"灵再。 "前綴"指除了最后一個字符以外肋层,一個字符串的全部頭部組合亿笤;"后綴"指除了第一個字符以外,一個字符串的全部尾部組合栋猖。

15.

"部分匹配值"就是"前綴"和"后綴"的最長的共有元素的長度净薛。以"ABCDABD"為例端圈,

- "A"的前綴和后綴都為空集邀杏,共有元素的長度為0;

- "AB"的前綴為[A]真朗,后綴為[B]雌团,共有元素的長度為0爆班;

- "ABC"的前綴為[A, AB],后綴為[BC, C]辱姨,共有元素的長度0;

- "ABCD"的前綴為[A, AB, ABC]戚嗅,后綴為[BCD, CD, D]雨涛,共有元素的長度為0;

- "ABCDA"的前綴為[A, AB, ABC, ABCD]懦胞,后綴為[BCDA, CDA, DA, A]替久,共有元素為"A",長度為1躏尉;

- "ABCDAB"的前綴為[A, AB, ABC, ABCD, ABCDA]蚯根,后綴為[BCDAB, CDAB, DAB, AB, B],共有元素為"AB"胀糜,長度為2颅拦;

- "ABCDABD"的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB],后綴為[BCDABD, CDABD, DABD, ABD, BD, D]教藻,共有元素的長度為0距帅。

16.

"部分匹配"的實(shí)質(zhì)是,有時候括堤,字符串頭部和尾部會有重復(fù)碌秸。比如,"ABCDAB"之中有兩個"AB"悄窃,那么它的"部分匹配值"就是2("AB"的長度)讥电。搜索詞移動的時候,第一個"AB"向后移動4位(字符串長度-部分匹配值)轧抗,就可以來到第二個"AB"的位置恩敌。


轉(zhuǎn)自阮一峰 字符串匹配的KMP算法

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市鸦致,隨后出現(xiàn)的幾起案子潮剪,更是在濱河造成了極大的恐慌涣楷,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,919評論 6 502
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件抗碰,死亡現(xiàn)場離奇詭異狮斗,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)弧蝇,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,567評論 3 392
  • 文/潘曉璐 我一進(jìn)店門碳褒,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人看疗,你說我怎么就攤上這事沙峻。” “怎么了两芳?”我有些...
    開封第一講書人閱讀 163,316評論 0 353
  • 文/不壞的土叔 我叫張陵摔寨,是天一觀的道長。 經(jīng)常有香客問我怖辆,道長是复,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,294評論 1 292
  • 正文 為了忘掉前任竖螃,我火速辦了婚禮淑廊,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘特咆。我一直安慰自己季惩,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,318評論 6 390
  • 文/花漫 我一把揭開白布腻格。 她就那樣靜靜地躺著画拾,像睡著了一般。 火紅的嫁衣襯著肌膚如雪菜职。 梳的紋絲不亂的頭發(fā)上碾阁,一...
    開封第一講書人閱讀 51,245評論 1 299
  • 那天,我揣著相機(jī)與錄音些楣,去河邊找鬼脂凶。 笑死,一個胖子當(dāng)著我的面吹牛愁茁,可吹牛的內(nèi)容都是我干的蚕钦。 我是一名探鬼主播,決...
    沈念sama閱讀 40,120評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼鹅很,長吁一口氣:“原來是場噩夢啊……” “哼嘶居!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 38,964評論 0 275
  • 序言:老撾萬榮一對情侶失蹤邮屁,失蹤者是張志新(化名)和其女友劉穎整袁,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體佑吝,經(jīng)...
    沈念sama閱讀 45,376評論 1 313
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡坐昙,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,592評論 2 333
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了芋忿。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片炸客。...
    茶點(diǎn)故事閱讀 39,764評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖戈钢,靈堂內(nèi)的尸體忽然破棺而出痹仙,到底是詐尸還是另有隱情,我是刑警寧澤殉了,帶...
    沈念sama閱讀 35,460評論 5 344
  • 正文 年R本政府宣布开仰,位于F島的核電站,受9級特大地震影響薪铜,放射性物質(zhì)發(fā)生泄漏抖所。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,070評論 3 327
  • 文/蒙蒙 一痕囱、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧暴匠,春花似錦鞍恢、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,697評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至窒典,卻和暖如春蟆炊,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背瀑志。 一陣腳步聲響...
    開封第一講書人閱讀 32,846評論 1 269
  • 我被黑心中介騙來泰國打工涩搓, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人劈猪。 一個月前我還...
    沈念sama閱讀 47,819評論 2 370
  • 正文 我出身青樓昧甘,卻偏偏與公主長得像,于是被迫代替她去往敵國和親战得。 傳聞我的和親對象是個殘疾皇子充边,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,665評論 2 354

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