摘要：寫(xiě)在最前本次分享一下通過(guò)實(shí)現(xiàn)算法的動(dòng)畫(huà)效果來(lái)試圖展示的基本思路。算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。本次主要通過(guò)動(dòng)畫(huà)演示的方式展現(xiàn)樸素算法與算法對(duì)比過(guò)程的異同從而試圖理解的基本思路。

本次分享一下通過(guò)實(shí)現(xiàn)kmp算法的動(dòng)畫(huà)效果來(lái)試圖展示kmp的基本思路。

歡迎關(guān)注我的博客，不定期更新中——

字符串匹配是計(jì)算機(jī)科學(xué)中最古老、研究最廣泛的問(wèn)題之一。一個(gè)字符串是一個(gè)定義在有限字母表∑上的字符序列。例如，ATCTAGAGA是字母表∑ = {A,C,G,T}上的一個(gè)字符串。字符串匹配問(wèn)題就是在一個(gè)大的字符串T中搜索某個(gè)字符串P的所有出現(xiàn)位置。

KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)，因此人們稱(chēng)它為克努特——莫里斯——普拉特操作（簡(jiǎn)稱(chēng)KMP算法）。KMP算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。具體實(shí)現(xiàn)就是實(shí)現(xiàn)一個(gè)next()函數(shù)，函數(shù)本身包含了模式串的局部匹配信息。時(shí)間復(fù)雜度O(m+n)。

在js中字符串匹配我們通常使用的是原生api，indexOf；其本身是c++實(shí)現(xiàn)的不在這次的討論范圍中。本次主要通過(guò)動(dòng)畫(huà)演示的方式展現(xiàn)樸素算法與kmp算法對(duì)比過(guò)程的異同從而試圖理解kmp的基本思路。

PS:在之后的敘述中BBC ABCDAB ABCDABCDABDE為主串；ABCDABD為模式串

上方為樸素算法即按位比較，下方為kmp算法實(shí)現(xiàn)的字符串比較方式。kmp可以通過(guò)較少的比較次數(shù)完成匹配。

從上圖的效果預(yù)覽中可以看出使用樸素算法依次比較模式串需要移位13次，而使用kmp需要8次，故可以說(shuō)kmp的思路是通過(guò)避免無(wú)效的移位，來(lái)快速移動(dòng)到指定的地點(diǎn)。接下來(lái)我們關(guān)注一下kmp是如何“跳著”移動(dòng)的：

與樸素算法一致，在之前對(duì)于主串“BBC ”的匹配中模式串ABCBABD的第一個(gè)字符均與之不同故向后移位到現(xiàn)在上圖所示的位置。主串通過(guò)依次與模式串中的字符比較我們可以看出，模式串的前6個(gè)字符與主串相同即ABCDAB；而這也就是kmp算法的關(guān)鍵。

我們先從下圖來(lái)看樸素算法與kmp中下一次移位的過(guò)程：

樸素算法雨打不動(dòng)得向后移了一位。而kmp跳過(guò)了主串的BCD三個(gè)字符。從而進(jìn)行了一次避免無(wú)意義的移位比較。那么它是怎么知道我這次要跳過(guò)三個(gè)而不是兩個(gè)或者不跳呢？關(guān)鍵在于上一次已經(jīng)匹配的部分ABCDAB

我們已知此時(shí)主串與模式串均有此相同的部分ABCDAB。那么如何從這共同部分中獲得有用的信息？或者換個(gè)角度想一下：我們能跳過(guò)部分位置的依據(jù)是什么？

第一次匹配失敗時(shí)的情形如下：

    BBC ABCDAB ABCDABCDABDE
        ABCDABD
              D != 空格 故失敗

為了從已匹配部分提取信息?，F(xiàn)在將主串做一下變形：

    ABCDABXXXXXX...  X可能是任何字符

我們現(xiàn)在只知道已匹配的部分，因?yàn)槠ヅ湟呀?jīng)失敗了不會(huì)再去讀取后面的字符，故用X代替。

那么我們能跳過(guò)多少位置的問(wèn)題就可以由下面的解得知答案：

    //ABCDAB向后移動(dòng)幾位可能能匹配上？
    ABCDABXXXXXX...
    ABCDABD

答案自然是如下移動(dòng)：

    ABCDABXXXXXX...
        ABCDABD

因?yàn)槲覀儾恢繶代表什么，只能從已匹配的串來(lái)分析。

故我們能跳過(guò)部分位置的依據(jù)是什么？

答：已匹配的模式串的前n位能否等于匹配部分的主串的后n位。并且n盡可能大。

舉個(gè)例子：

//第一次匹配失敗時(shí)匹配到ABCDDDABC為共同部分
    XXXABCDDDABCFXXX
       ABCDDDABCE
//尋找模式串的最大前幾位與主串匹配到的部分后幾位相同，
//可以發(fā)現(xiàn)最多是ABC部分相同，故可以略過(guò)DDD的匹配因?yàn)榭隙▽?duì)不上
    XXXABCDDDABCFXXX
             ABCDDDABCE     

現(xiàn)在kmp的基本思路已經(jīng)很明顯了，其就是通過(guò)經(jīng)失敗后得知的已匹配字段，來(lái)尋找主串尾部與模式串頭部的相同最大匹配，如果有則可以跨過(guò)中間的部分，因?yàn)樗^“中間”的部分，也是有可能進(jìn)入主串尾與模式串頭的，沒(méi)進(jìn)去的原因即是相對(duì)位置字符不同，故最終在模式串移位時(shí)可以跳過(guò)。

上面是用通俗的話來(lái)述說(shuō)我們?nèi)绾胃鶕?jù)已匹配的部分來(lái)決定下一次模式串移位的位置，大家應(yīng)該已經(jīng)大體知道kmp的思路了。現(xiàn)在來(lái)引出官方的說(shuō)法。

之前敘述的在已匹配部分中查找主串頭部與模式串尾部相同的部分的結(jié)果我們可以用部分匹配值的說(shuō)法來(lái)形容：

其中定義"前綴"和"后綴"。"前綴"指除了最后一個(gè)字符以外，一個(gè)字符串的全部頭部組合；"后綴"指除了第一個(gè)字符以外，一個(gè)字符串的全部尾部組合。

"部分匹配值"就是"前綴"和"后綴"的最長(zhǎng)的共有元素的長(zhǎng)度。

例如ABCDAB

前綴分別為A、AB、ABC、ABCD、ABCDA

后綴分別為B、AB、DAB、CDAB、BCDAB

很容易發(fā)現(xiàn)部分匹配值為2即AB的長(zhǎng)度。從而結(jié)合之前的思路可以知道將模式串直接移位到主串AB對(duì)應(yīng)的地方即可，中間的部分一定是不匹配的。移動(dòng)幾位呢？

答：匹配串長(zhǎng)度 - 部分匹配值；本次例子中為6-2=4，模式串向右移動(dòng)四位

function pmtArr(target) {
    var pmtArr = []
    target = target.split("")
    for(var j = 0; j < target.length; j++) {
    //獲取模式串不同長(zhǎng)度下的部分匹配值
        var pmt = target
        var pmtNum = 0
        for (var k = 0; k < j; k++) {
            var head = pmt.slice(0, k + 1) //前綴
            var foot = pmt.slice(j - k, j + 1) //后綴
            if (head.join("") === foot.join("")) {
                var num = head.length
                if (num > pmtNum) pmtNum = num
            }
        }
        pmtArr.push(j + 1 - pmtNum) 
    }
    return pmtArr
}

function mapKMPStr(base, target) {
    var isMatch = []
    var pmt = pmtArr(target)
    console.time("kmp")
    var times = 0
    for(var i = 0; i < base.length; i++) {
        times++
        var tempIndex = 0
        for(var j = 0; j < target.length; j++) {
            if(i + target.length <= base.length) {
                if (target.charAt(j) === base.charAt(i + j)) {
                    isMatch.push(target.charAt(j))
                } else {
                    if(!j) break //第一個(gè)就不匹配直接跳到下一個(gè)
                    var skip = pmt[j - 1]
                    tempIndex = i + skip - 1
                    break 
                }
            }
        }
        var data = {
            index: i,
            matchArr: isMatch
        }
        callerKmp.push(data)
        if(tempIndex) i = tempIndex
        if(isMatch.length === target.length) {
            console.timeEnd("kmp")
            console.log("移位次數(shù):", times)
            return i
        }
        isMatch = []
    }
    console.timeEnd("kmp")
    return -1

有了思路后整體實(shí)現(xiàn)并不復(fù)雜，只需要先通過(guò)模式串計(jì)算各長(zhǎng)度的部分匹配值，在之后的與主串的匹配過(guò)程中，每失敗一次后如果有部分匹配值存在，我們就可以通過(guò)部分匹配值查找到下一次應(yīng)該移位的位置，省去不必要的步驟。

所以在某些極端情況下，比如需要搜索的詞如果內(nèi)部完全沒(méi)有重復(fù)，算法就會(huì)退化成遍歷，性能可能還不如傳統(tǒng)算法，里面還涉及了比較的開(kāi)銷(xiāo)。

字符串匹配的KMP算法

慣例po作者的博客，不定時(shí)更新中——

有問(wèn)題歡迎在issues下交流。