一、數(shù)據(jù)結(jié)構(gòu)中KMP算法
KMP算法介紹
KMP算法是一種改進(jìn)的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人們稱它為克努特—莫里斯—普拉特操作(簡(jiǎn)稱KMP算法)。KMP算法是在 BF 算法基礎(chǔ)上改進(jìn)得到的算法。學(xué)習(xí) BF 算法我們知道,該算法的實(shí)現(xiàn)過程就是 “傻瓜式” 地用模式串(假定為子串的串)與主串中的字符一一匹配,匹配不成功則返回到上一次與主串匹配的下一位字符進(jìn)行匹配,算法執(zhí)行效率不高。
KMP算法的解決題型
KMP算法是在數(shù)據(jù)結(jié)構(gòu)中兩個(gè)字符串相互匹配衍生出來的算法。KMP算法的作用是在一個(gè)已知字符串中查找子串的位置,也叫做串的模式匹配。例如,對(duì)主串 A(“ABCABCE”)和模式串 B(“ABCE”)進(jìn)行模式匹配,如果人為去判斷,僅需匹配兩次。雖然在以上字符較少的串中人為匹配很容易,但是讓計(jì)算機(jī)來匹配就相對(duì)慢一些,但是當(dāng)字符串中的字符非常多的時(shí)候,就不可能人為去匹配。所以打鐵還需自身硬,我們把這種枯燥的事以一定的算法交給計(jì)算機(jī)處理。
KMP算法相比BF算法的改進(jìn)
每當(dāng)一趟匹配過程中出現(xiàn)字符比較不等時(shí),無需回溯i指針(即無需將i指針完全退回至i-j+1),而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后,繼續(xù)進(jìn)行比較。
需要解決的問題:當(dāng)主串中的第i個(gè)字符與模式中第j個(gè)字符比較不相等時(shí),主串中第i個(gè)字符(i指針不回溯)應(yīng)與模式中哪個(gè)字符再比較?—-假設(shè)從主串中第i個(gè)字符與模式中的第k個(gè)字符再進(jìn)行比較
它是則呢樣來消除回溯的呢?就是因?yàn)樗崛〔⑦\(yùn)用了加速匹配的信息!
這種信息就是對(duì)于每模式串 t 的每個(gè)元素 t j,都存在一個(gè)實(shí)數(shù) k ,使得模式串 t 開頭的 k 個(gè)字符(t 0 t 1…t k-1)依次與 t j 前面的 k(t j-k t j-k+1…t j-1,這里名列前茅個(gè)字符 t j-k 非常多從 t 1 開始,所以 k < j)個(gè)字符相同。如果這樣的 k 有多個(gè),則取最大的一個(gè)。模式串 t 中每個(gè)位置 j 的字符都有這種信息,采用 next 數(shù)組表示,即 next[ j ]=MAX{ k }。
延伸閱讀:
二、KMP算法的時(shí)間復(fù)雜度
主要由兩部分組成:預(yù)處理部分和匹配部分。
預(yù)處理部分:在這一步,算法計(jì)算模式串的最長(zhǎng)公共前綴和后綴(也稱為部分匹配表或失效函數(shù))。這一步的時(shí)間復(fù)雜度為O(m),因?yàn)樗闅v了整個(gè)模式串。匹配部分:在這一步,算法在目標(biāo)文本中查找模式串。在最壞的情況下,這一步的時(shí)間復(fù)雜度為O(n)。這是因?yàn)樗惴ㄔ谶M(jìn)行比較時(shí),可以根據(jù)失效函數(shù)跳過不匹配的字符,因此,它不需要對(duì)每個(gè)字符進(jìn)行逐一比較。綜合考慮這兩部分,KMP算法的總時(shí)間復(fù)雜度為O(m+n)。與樸素的字符串匹配算法相比(其時(shí)間復(fù)雜度為O(mn)),KMP算法具有更高的效率,尤其在處理大量數(shù)據(jù)時(shí)。