概述:本文主要在理論層面上分析KMP的基本實(shí)現(xiàn)原理以及《部分匹配表》推導(dǎo)過程;不涉及代碼實(shí)現(xiàn);如果您對KMP的實(shí)現(xiàn)代碼(OC)實(shí)現(xiàn)感興趣,可參考:
KMP(一) 模式匹配算法推導(dǎo) --《部分匹配表》
KMP(二) 模式匹配算法實(shí)現(xiàn)
KMP(三) 字符串快速匹配示例
一: KMP主要解決的問題:
KMP是三位大牛：D.E.Knuth凰慈、J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)的死宣。其中第一位就是《計算機(jī)程序設(shè)計藝術(shù)》的作者Ｇ绻 唁奢！
KMP算法要解決的問題就是在字符串（也叫主串,下文統(tǒng)一稱"P"）中快速高效匹配子串(下文統(tǒng)一稱"S")并確定S在P中位置的問題积暖。說簡單點(diǎn)就是我們平時常說的關(guān)鍵字(詞)搜索乎婿。
二. 字串樸素匹配算法實(shí)現(xiàn):
看一個樸素匹配算法示例:
主串: P="BBC ABCDAB ABCDABCDABDE" 長度為Length_p
字串: S = "ABCDABD" 長度為Length_s
首先今阳，字符串"BBC ABCDAB ABCDABCDABDE"的第一個字符與搜索詞"ABCDABD"的第一個字符，進(jìn)行比較逊躁。因?yàn)锽與A不匹配似踱，所以搜索詞后移一位。
因?yàn)锽與A不匹配稽煤，搜索詞再往后移核芽。
就這樣，直到字符串有一個字符酵熙，與搜索詞的第一個字符相同為止轧简。
接著比較字符串和搜索詞的下一個字符，還是相同匾二。
直到字符串有一個字符哮独，與搜索詞對應(yīng)的字符不相同為止。
這時察藐，最自然的反應(yīng)是借嗽，將搜索詞整個后移一位，再從頭逐個比較转培。這樣做雖然可行，但是效率很差浆竭，因?yàn)槟阋?搜索位置"移到已經(jīng)比較過的位置浸须，重比一遍,很明顯P的位置在回溯惨寿。分析樸素匹配算法時間復(fù)雜度為:
O((Length_p - Length_s + 1) * Length_s)
為方便后續(xù)說明,我們來約定一組表達(dá)規(guī)則:
主串 P 和字串 S 中有以下表達(dá),示例如:
P[0] = "B"
P[4] = "A"
P[0~5]="BBC AB"
S[0] = "A"
S[2]="C"
S[1~3]="BCD"
我們觀察一下此時字串 S 和 主串P:
以下重要:
當(dāng)S[0~5] = P[4~9] 并且 S[6] != P[10]時,S[0~3] 內(nèi)沒有重復(fù)的字符,而切S[0~3] =P[4~7],所以在進(jìn)行下一次比較時,我們可以直接將字串S移動至主串P的P[8] 位置開始比較,同時保持P的上一次查找位置不變(P[10]), 而不是像上圖一樣從P[5]開始循環(huán)比較,因?yàn)榇藭r的P[5~8] 不可能與S(主要看S[0~3])匹配 ;這樣效率會大大提升;接下來看KMP是如何做的;
三. KMP算法示例分析:
KMP核心原則: 保持主串P上次查找位置(index_p)不回溯,移動字串S到合適的位置(index_s),下次比較起始位置分別為P[index_p]和S[index_s],不在比較P[0~index_p] 和 S[0~index_s],從而達(dá)到簡化匹配的計算過程;具體示例如下:
這里要引入一個《部分匹配表》概念;部分匹配表推導(dǎo)過程稍后做解釋;我們要做的先學(xué)會如何利用《部分匹配表》去實(shí)現(xiàn)KMP模式匹配,從而理解KMP的匹配過程;字串移位計算公式如下:
移動位數(shù)(S) = 已匹配的字符數(shù) - 對應(yīng)的部分匹配值
接著上述利用《部分匹配表》匹配分析:
7.
已知空格與D不匹配時，前面6個字符"ABCDAB"是匹配的删窒。查表可知裂垦，最后一個匹配字符B對應(yīng)的"部分匹配值"為2，照上面的公式算出向后移動的位數(shù)：
因?yàn)?6 - 2 等于4肌索，所以將S向后移動4位蕉拢。
8.
因?yàn)榭崭衽cＣ不匹配，搜索詞還要繼續(xù)往后移诚亚。這時晕换，已匹配的字符數(shù)為2（"AB"），對應(yīng)B的"部分匹配值"為0站宗。所以闸准，移動位數(shù) = 2 - 0，結(jié)果為 2梢灭，于是將搜索詞向后移2位夷家。
9.
因?yàn)榭崭衽cA不匹配，而S已經(jīng)到達(dá)最左端,故P繼續(xù)后移一位敏释。
10.
逐位比較库快，直到發(fā)現(xiàn)C與D不匹配。于是钥顽，移動位數(shù) = 6 - 2义屏，繼續(xù)將搜索詞向后移動4位。
11.
逐位比較耳鸯，直到搜索詞的最后一位湿蛔，發(fā)現(xiàn)完全匹配，于是搜索完成县爬。如果還要繼續(xù)搜索（即找出全部匹配）阳啥，移動位數(shù) = 7 - 0，再將搜索詞向后移動7位财喳，這里就不再重復(fù)了察迟。
四. 《部分匹配表》計算過程
首先，要了解兩個概念："前綴"和"后綴"耳高。 "前綴"指除了最后一個字符以外扎瓶，一個字符串的全部頭部組合；"后綴"指除了第一個字符以外泌枪，一個字符串的全部尾部組合概荷。注意:此處有個組合的概念,表達(dá)不同于KMP 算法實(shí)現(xiàn)中的前綴和后綴
"部分匹配值"就是"前綴"和"后綴"的最長的共有元素的長度。以"ABCDABD"為例碌燕，
1. "A"的前綴和后綴都為空集误证，共有元素的長度為0继薛；
2. "AB"的前綴為[A]，后綴為[B]愈捅，共有元素的長度為0遏考；
3. "ABC"的前綴為[A, AB]，后綴為[BC, C]蓝谨，共有元素的長度0灌具；
4. "ABCD"的前綴為[A, AB, ABC]，后綴為[BCD, CD, D]譬巫，共有元素的長度為0咖楣；
5. "ABCDA"的前綴為[A, AB, ABC, ABCD]，后綴為[BCDA, CDA, DA, A]缕题，共有元素為"A"截歉，長度為1；
6. "ABCDAB"的前綴為[A, AB, ABC, ABCD, ABCDA]烟零，后綴為[BCDAB, CDAB, DAB, AB, B]瘪松，共有元素為"AB"，長度為2锨阿；
7. "ABCDABD"的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]宵睦，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為0墅诡。
