KMP算法中的優(yōu)化應(yīng)用探討

劉國(guó)慶 史小春

【摘要】 無回溯的模式匹配中最具代表性的是KMP算法。它是基于對(duì)模式本身的字符分布特征所進(jìn)行的分析，生成模式的特征向量，并在模式匹配的過程中對(duì)此加以利用，以提高模式匹配的效率，其時(shí)間代價(jià)是目標(biāo)串長(zhǎng)度的線性函數(shù)，同時(shí)模式的特征向量的計(jì)算也與模式本身長(zhǎng)度成正比。在KMP算法中最關(guān)鍵的部分是模式的特征向量的計(jì)算和生成。

【關(guān)鍵詞】 KMP算法 優(yōu)化應(yīng)用

在KMP算法中有個(gè)數(shù)組，叫做前綴數(shù)組，也有的叫next數(shù)組，每一個(gè)子串有一個(gè)固定的next數(shù)組，它記錄著字符串匹配過程中失配情況下可以向前多跳幾個(gè)字符，當(dāng)然它描述的也是子串的對(duì)稱程度，程度越高，值越大，當(dāng)然之前可能出現(xiàn)再匹配的機(jī)會(huì)就更大。

這個(gè)next數(shù)組的求法是KMP算法的關(guān)鍵：對(duì)稱串；

1、用一個(gè)例子來解釋，下面是一個(gè)子串的next數(shù)組的值，可以看到這個(gè)子串的對(duì)稱程度很高，所以next值都比較大。

申明一下：下面說的對(duì)稱不是中心對(duì)稱，而是中心字符塊對(duì)稱，比如不是abccba，而是abcabc這種對(duì)稱。

（1）逐個(gè)查找對(duì)稱串。

這個(gè)很簡(jiǎn)單，我們只要循環(huán)遍歷這個(gè)子串，分別看前1個(gè)字符，前2個(gè)字符，3個(gè)... i個(gè) 最后到15個(gè)。

第1個(gè)a無對(duì)稱，所以對(duì)稱程度0；前兩個(gè)ag無對(duì)稱，所以也是0；依次類推前面0-4都一樣是0；前5個(gè)agcta，可以看到這個(gè)串有一個(gè)a相等，所以對(duì)稱程度為1前6個(gè)agctag，看得到ag和ag對(duì)成，對(duì)稱程度為2；這里要注意了，想是這樣想，編程怎么實(shí)現(xiàn)呢？

只要按照下面的規(guī)則：a、當(dāng)前面字符的前一個(gè)字符的對(duì)稱程度為0的時(shí)候，只要將當(dāng)前字符與子串第一個(gè)字符進(jìn)行比較。這個(gè)很好理解啊，前面都是0，說明都不對(duì)稱了，如果多加了一個(gè)字符，要對(duì)稱的話最多是當(dāng)前的和第一個(gè)對(duì)稱。比如agcta這個(gè)里面t的是0，那么后面的a的對(duì)稱程度只需要看它是不是等于第一個(gè)字符a了。b、按照這個(gè)推理，我們就可以總結(jié)一個(gè)規(guī)律，不僅前面是0呀，如果前面一個(gè)字符的next值是1，那么我們就把當(dāng)前字符與子串第二個(gè)字符進(jìn)行比較，因?yàn)榍懊娴氖?，說明前面的字符已經(jīng)和第一個(gè)相等了，如果這個(gè)又與第二個(gè)相等了，說明對(duì)稱程度就是2了。有兩個(gè)字符對(duì)稱了。比如上面agctag，倒數(shù)第二個(gè)a的next是1，說明它和第一個(gè)a對(duì)稱了，接著我們就把最后一個(gè)g與第二個(gè)g比較，又相等，自然對(duì)稱成都就累加了，就是2了。 c、按照上面的推理，如果一直相等，就一直累加，可以一直推啊，推到這里應(yīng)該一點(diǎn)難度都沒有吧。

當(dāng)然不可能會(huì)那么順利讓我們一直對(duì)稱下去，如果遇到下一個(gè)不相等了，那么說明不能繼承前面的對(duì)稱性了，這種情況只能說明沒有那么多對(duì)稱了，但是不能說明一點(diǎn)對(duì)稱性都沒有，所以遇到這種情況就要重新來考慮，這個(gè)也是難點(diǎn)所在。

（2）回頭來找對(duì)稱性

這里已經(jīng)不能繼承前面了，但是還是找對(duì)稱程度，最不可取的做法是寫一個(gè)子函數(shù)，查找這個(gè)字符串的最大對(duì)稱程度，怎么寫方法很多，比如查找出所有的當(dāng)前字符串，然后向前走，看是否一直相等，最后走到子串開頭，當(dāng)然這個(gè)是效率最低的，我們一般看到的KMP都是優(yōu)化過的，因?yàn)檫@個(gè)串是有規(guī)律的。在這里依然用上面表中一段來舉個(gè)例子：

位置i=0到14如下，我加的括號(hào)只是用來說明問題：

我們可以看到這段，最后這個(gè)t之前的對(duì)稱程度分別是：1，2，3，4，5，6，7，倒數(shù)第二個(gè)c往前看有7個(gè)字符對(duì)稱，所以對(duì)稱為7。但是到最后這個(gè)t就沒有繼承前面的對(duì)稱程度next值，所以這個(gè)t的對(duì)稱性就要重新來求。

這里首要要申明幾個(gè)事實(shí)1、t 如果要存在對(duì)稱性，那么對(duì)稱程度肯定比前面這個(gè)c 的對(duì)稱程度小，所以要找個(gè)更小的對(duì)稱，這個(gè)不用解釋了吧，如果大那么t就繼承前面的對(duì)稱性了。2、要找更小的對(duì)稱，必然在對(duì)稱內(nèi)部還存在子對(duì)稱，而且這個(gè)t必須緊接著在子對(duì)稱之后。