這篇文章主要介紹了JavaScript中數(shù)據(jù)結(jié)構(gòu)與算法(五)：經(jīng)典KMP算法,本文詳解了KMP算法的方方面在,需要的朋友可以參考下

　　KMP算法和BM算法

　　KMP是前綴匹配和BM后綴匹配的經(jīng)典算法，看得出來前綴匹配和后綴匹配的區(qū)別就僅僅在于比較的順序不同

　　前綴匹配是指：模式串和母串的比較從左到右，模式串的移動(dòng)也是從 左到右

　　后綴匹配是指：模式串和母串的的比較從右到左，模式串的移動(dòng)從左到右。

　　通過上一章顯而易見BF算法也是屬于前綴的算法，不過就非常霸蠻的逐個(gè)匹配的效率自然不用提了O(mn)，網(wǎng)上蛋疼的KMP是講解很多，基本都是走的高大上路線看的你也是一頭霧水，我試圖用自己的理解用最接地氣的方式描述

　　KMP

　　KMP也是一種優(yōu)化版的前綴算法，之所以叫KMP就是Knuth、Morris、Pratt三個(gè)人名的縮寫，對比下BF那么KMP的算法的優(yōu)化點(diǎn)就在“每次往后移動(dòng)的距離”它會(huì)動(dòng)態(tài)的調(diào)整每次模式串的移動(dòng)距離，BF是每次都+1，

　　KMP則不一定

　　如圖BF與KMP前置算法的區(qū)別對比

　　我通過圖對比我們發(fā)現(xiàn)：

　　在文本串T中搜索模式串P，在自然匹配第6個(gè)字母c的時(shí)候發(fā)現(xiàn)二等不一致了，那么BF的方法，就是把整個(gè)模式串P移動(dòng)一位，KMP則是移動(dòng)二位.

　　BF的匹配方法我們是知道的，但是KMP為什么會(huì)移動(dòng)二位，而不是一位或者三位四位呢?

　　這就上一張圖我們講解下，模式串P在匹配了ababa的時(shí)候都是正確的，當(dāng)?shù)絚的時(shí)候才是錯(cuò)誤，那么KMP算法的想法是：ababa是正確的匹配完成的信息，我們能不能利用這個(gè)信息，不要把"搜索位置"移回已經(jīng)比較過的位置，繼續(xù)把它向后移，這樣就提高了效率。

　　那么問題來了, 我怎么知道要移動(dòng)多少個(gè)位置?

　　這個(gè)偏移的算法KMP的作者們就給我們總結(jié)好了：

　　代碼如下:

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

　　偏移算法只跟子串有關(guān)系，沒文本串沒毛線關(guān)系，所以這里需要特別注意了

　　那么我們怎么理解子串中已匹配的字符數(shù)與對應(yīng)的部分匹配值?

　　已匹配的字符：

　　 代碼如下:

　　T : abababaabab

　　p : ababacb

　　p中紅色的標(biāo)記就是已經(jīng)匹配的字符，這個(gè)很好理解

　　部分匹配值：

　　這個(gè)就是核心的算法了，也是比較難于理解的

　　假如：

　　 代碼如下:

　　T：aaronaabbcc

　　P：aaronaac

　　我們可以觀察這個(gè)文本如果我們在匹配c的時(shí)候出錯(cuò)，我們下一個(gè)移動(dòng)的位置就上個(gè)的結(jié)構(gòu)來講，移動(dòng)到那里最合理?

　　 代碼如下:

　　aaronaabbcc

　　aaronaac

　　那么就是說：在模式文本內(nèi)部，某一段字符頭尾都一樣，那么自然過濾的時(shí)候可以跳過這一段內(nèi)容了，這個(gè)思路也是合理的

　　知道了這個(gè)規(guī)律，那么給出來的部分匹配表算法如下：

　　首先，要了解兩個(gè)概念："前綴"和"后綴"。 "前綴"指除了最后一個(gè)字符以外，一個(gè)字符串的全部頭部組合;"后綴"指除了第一個(gè)字符以外，一個(gè)字符串的全部尾部組合。

　　"部分匹配值"就是"前綴"和"后綴"的最長的共有元素的長度”

　　我們看看aaronaac的如果是BF匹配的時(shí)候劃分是這樣的

　　BF的位移: a,aa,aar,aaro,aaron,aarona,aaronaa,aaronaac

　　那么KMP的劃分呢?這里就要引入前綴與后綴了

　　我們先看看KMP部分匹配表的結(jié)果是這樣的：

　　代碼如下:

　　a a r o n a a c

　　[0, 1, 0, 0, 0, 1, 2, 0]