JavaScript中數據結構與算法(五)：經典KMP算法

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

　　KMP算法和BM算法

　　KMP是前綴匹配和BM後綴匹配的經典算法，看得出來前綴匹配和後綴匹配的區別就僅僅在於比較的順序不同

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

　　後綴匹配是指：模式串和母串的的比較從右到左，模式串的移動從左到右。

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

　　KMP

　　KMP也是一種優化版的前綴算法，之所以叫KMP就是Knuth、Morris、Pratt三個人名的縮寫，對比下BF那麼KMP的算法的優化點就在“每次往後移動的距離”它會動態的調整每次模式串的移動距離，BF是每次都+1，

　　KMP則不一定

　　如圖BF與KMP前置算法的區別對比

　　我通過圖對比我們發現：

　　在文本串T中搜索模式串P，在自然匹配第6個字母c的時候發現二等不一致了，那麼BF的方法，就是把整個模式串P移動一位，KMP則是移動二位.

　　BF的匹配方法我們是知道的，但是KMP為什麼會移動二位，而不是一位或者三位四位呢?

　　這就上一張圖我們講解下，模式串P在匹配了ababa的時候都是正確的，當到c的時候才是錯誤，那麼KMP算法的想法是：ababa是正確的匹配完成的信息，我們能不能利用這個信息，不要把"搜索位置"移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。

　　那麼問題來了, 我怎麼知道要移動多少個位置?

　　這個偏移的算法KMP的作者們就給我們總結好了：

　　代碼如下:

　　移動位數 = 已匹配的字符數 - 對應的部分匹配值

　　偏移算法只跟子串有關系，沒文本串沒毛線關系，所以這裡需要特別注意了

　　那麼我們怎麼理解子串中已匹配的字符數與對應的部分匹配值?

　　已匹配的字符：

　　 代碼如下:

　　T : abababaabab

　　p : ababacb

　　p中紅色的標記就是已經匹配的字符，這個很好理解

　　部分匹配值：

　　這個就是核心的算法了，也是比較難於理解的

　　假如：

　　 代碼如下:

　　T：aaronaabbcc

　　P：aaronaac

　　我們可以觀察這個文本如果我們在匹配c的時候出錯，我們下一個移動的位置就上個的結構來講，移動到那裡最合理?

　　 代碼如下:

　　aaronaabbcc

　　aaronaac

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

　　知道了這個規律，那麼給出來的部分匹配表算法如下：

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

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

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

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

　　那麼KMP的劃分呢?這裡就要引入前綴與後綴了

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

　　代碼如下:

　　a a r o n a a c

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

　　肯定是一頭霧水，不急我們分解下，前綴與後綴

　　 代碼如下:

　　匹配字符串 ：“Aaron”

　　前綴：A，Aa, Aar ,Aaro

　　後綴：aron,ron,on,n

　　移動的位置：其實就是針對每一個已匹配的字符做前綴與後綴的對比是否相等，然後算出共有的長度

　　部分匹配表的分解

　　KMP中的匹配表的算法，其中p表示前綴，n表示後綴，r表示結果

　　代碼如下:

　　a, p=>0, n=>0 r = 0

　　aa, p=>[a]，n=>[a] , r = a.length => 1

　　aar, p=>[a,aa], n=>[r,ar] ,r = 0

　　aaro, p=>[a,aa,aar], n=>[o,ra,aro] ,r = 0

　　aaron p=>[a,aa,aar,aaro], n=>[n,on,ron,aron] ,r = 0

　　aarona, p=>[a,aa,aar,aaro,aaron], n=>[a,na,ona,rona,arona] ,r = a.lenght = 1

　　aaronaa, p=>[a,aa,aar,aaro,aaron,aarona], n=>[a,aa,naa,onaa,ronaa,aronaa] , r = Math.max(a.length,aa.length) = 2

　　aaronaac p=>[a,aa,aar,aaro,aaron,aarona], n=>[c,ac,aac,naac,onaac,ronaac] r = 0

　　類似BF算法一下，先分解每一次可能匹配的下標的位置先緩存起來，在匹配的時候通過這個《部分匹配表》來定位需要後移動的位數

　　所以最後aaronaac的匹配表的結果 0,1,0,0,0,1,2,0 就是這麼來的

　　下面將會實現JS版的KMP，有2種

　　KMP實現(一)：緩存匹配表的KMP

　　KMP實現(二)：動態計算next的KMP

　　KMP實現(一)

　　匹配表

　　KMP算法中最重要的就是匹配表，如果不要匹配表那就是BF的實現，加上匹配表就是KMP了

　　匹配表決定了next下一個位移的計數

　　針對上面匹配表的規律，我們設計一個kmpGetStrPartMatchValue的方法

　　?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 function kmpGetStrPartMatchValue(str) { var prefix = []; var suffix = []; var partMatch = []; for (var i = 0, j = str.length; i < j; i++) { var newStr = str.substring(0, i + 1); if (newStr.length == 1) { partMatch[i] = 0; } else { for (var k = 0; k < i; k++) { //前綴 prefix[k] = newStr.slice(0, k + 1); //後綴 suffix[k] = newStr.slice(-k - 1); //如果相等就計算大小,並放入結果集中 if (prefix[k] == suffix[k]) { partMatch[i] = prefix[k].length; } } if (!partMatch[i]) { partMatch[i] = 0; } } } return partMatch; }

　　完全按照KMP中的匹配表的算法的實現，通過str.substring(0, i + 1) 分解a->aa->aar->aaro->aaron->aarona->aaronaa-aaronaac

　　然後在每一個分解中通過前綴後綴算出共有元素的長度

　　回退算法

　　KMP也是前置算法，完全可以把BF那一套搬過來，唯一修改的地方就是BF回溯的時候直接是加1，KMP在回溯的時候我們就通過匹配表算出這個next值即可

　　?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 //子循環 for (var j = 0; j < searchLength; j++) { //如果與主串匹配 if (searchStr.charAt(j) == sourceStr.charAt(i)) { //如果是匹配完成 if (j == searchLength - 1) { result = i - j; break; } else { //如果匹配到了，就繼續循環，i++是用來增加主串的下標位 i++; } } else { //在子串的匹配中i是被疊加了 if (j > 1 && part[j - 1] > 0) { i += (i - j - part[j - 1]); } else { //移動一位 i = (i - j) } break; } }

　　紅色標記的就是KMP的核心點 next的值 = 已匹配的字符數 - 對應的部分匹配值

　　完整的KMP算法

　　?

1 2