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

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

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

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

KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱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)的不在這次的討論范圍中。本次主要通過動畫演示的方式展現(xiàn)樸素算法與kmp算法對比過程的異同從而試圖理解kmp的基本思路。

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

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

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

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

我們先從下圖來看樸素算法與kmp中下一次移位的過程：

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

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

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

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

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

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

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

那么我們能跳過多少位置的問題就可以由下面的解得知答案：

    //ABCDAB向后移動幾位可能能匹配上？
    ABCDABXXXXXX...
    ABCDABD

答案自然是如下移動：

    ABCDABXXXXXX...
        ABCDABD

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

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

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

舉個(gè)例子：

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

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

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

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

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

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

例如ABCDAB

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

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

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

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

function pmtArr(target) {
    var pmtArr = []
    target = target.split("")
    for(var j = 0; j < target.length; j++) {
    //獲取模式串不同長度下的部分匹配值
        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ù)雜，只需要先通過模式串計(jì)算各長度的部分匹配值，在之后的與主串的匹配過程中，每失敗一次后如果有部分匹配值存在，我們就可以通過部分匹配值查找到下一次應(yīng)該移位的位置，省去不必要的步驟。

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

字符串匹配的KMP算法

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

有問題歡迎在issues下交流。