算法舉例來說绘闷,有一個字符串"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算法