KMP算法目的：盡快解決字符串匹配問題，時間復(fù)雜度為O(m+n)，而常規(guī)的簡單匹配算法時間復(fù)雜度：O(m*n)

這個算法不太容易理解，而且網(wǎng)上很多關(guān)于KMP算法的文章讀起來很費(fèi)勁，以下，我按照自己的理解，試著寫一篇易懂的算法解釋。

1 關(guān)于模式的前后綴函數(shù)(next數(shù)組獲取)

首先，為了方便后面的描述，先定義下：S表示原字符串，T表示目標(biāo)字符串(模式串)，關(guān)于字符串匹配，就是在S中尋找T。

關(guān)于尋找字符串的前后綴，舉個例子：
字符串：abcab
前綴：a，ab，abc，abca
后綴：bcab，cab，ab，b

“前綴”指除了最后一個字符以外，一個字符串全部頭部組合。
“后綴”指除了第一個字符以外，一個字符串全部尾部組合。

模式前后綴函數(shù)，就是產(chǎn)生一個長度等于模式串T長度的數(shù)組，每個值為相應(yīng)“部分匹配值”的數(shù)組。
“部分匹配值”就是“前綴”和“后綴”的最長的共有元素字符串的長度。以“ABCDABD”為例：

• "A"的前綴和后綴都為空集，共有元素的長度為__ 0 __；
• "AB"的前綴為[A]，后綴為[B]，共有元素的長度為__ 0 __；
• "ABC"的前綴為[A, AB]，后綴為[BC, C]，共有元素的長度__ 0 __；
• "ABCD"的前綴為[A, AB, ABC]，后綴為[BCD, CD, D]，共有元素的長度為__ 0 __；
• "ABCDA"的前綴為[A, AB, ABC, ABCD]，后綴為[BCDA, CDA, DA, A]，共有元素為"A"，長度為__ 1 __；
• "ABCDAB"的前綴為[A, AB, ABC, ABCD, ABCDA]，后綴為[BCDAB, CDAB, DAB, AB, B]，共有元素為"AB"，長度為__ 2 __；
• "ABCDABD"的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為__ 0 __。

所以，對于字符串"ABCDABD"，會相應(yīng)地產(chǎn)生一個數(shù)組array(0, 0, 0, 0, 1, 2, 0)。這就是KMP算法關(guān)于next數(shù)組(也就是計算前后綴函數(shù))原理，它記錄的是模式串T子串(T[0 ... j] 0 < j < n)的最長前后綴元素長度的信息。

接下來，介紹KMP算法思想。

2 KMP算法思想

第一次：

第二次：

傳統(tǒng)匹配算法中，每一輪匹配過后，都會回溯到T[0]和S[i+1]的狀態(tài)位置開始下一輪的匹配。而上面的表圖運(yùn)用了KMP算法，顯然兩次就能得出匹配信息：
這里先給出模式串T("abcabd")的next數(shù)組參照:

第一個表格中，S[5]與T[5]匹配失敗時，T[0 ... 4]字符串最長“前-后綴”是"ab"，它在T[0 ... 4]中對應(yīng)的前綴是T[0 ... 1]，后綴是T[3 ... 4] (前后綴相等)，既然T[0 ... 4]與S[0 ... 4]匹配成功，那么T[0 ... 1]必然與S[3 ... 4]完全匹配。(先結(jié)合next獲取那段好好理解)

由此可以想到，當(dāng)S[i]與T[j]匹配失敗時，如果我們知道T[0 ... j-1]最長“前-后綴”在T[0 ... j - 1]對應(yīng)的前綴是T[0 ... m] (m = next[j-1] - 1)，那么我們可以直接將S[i]與T[m+1]對齊，開始下次匹配，因為T[0 ... m]必然已經(jīng)與S[0 ... i - 1]的后綴匹配成功。避免了不必要的回溯

下面是KMP算法代碼：

    def `kmp-matcher` (s: String, t: String): Int = {
        val next = `init-next`(t)

        val s_len = s.length
        val t_len = t.length

        var i = 0   /*記錄原字符串下標(biāo)*/
        var j = 0   /*記錄模式串下標(biāo)*/

        while (i < s_len && s_len - i > t_len - j) {
            while (j < t_len /*注意先檢查下標(biāo)越界*/ && s.charAt(i) == t.charAt(j)) {
                i = i + 1
                j = j + 1
            }

            /*
             * 下面有兩種分支，完全匹配和匹配中斷
             * 完全匹配：函數(shù)直接返回匹配時的坐標(biāo)
             * 匹配中斷：設(shè)置i，j下標(biāo)，使其S[i]與T[NEXT[j-1]]對齊，進(jìn)行下一次匹配
             */

            if (j == t_len /*完全匹配，此處直接返回此次匹配首位下標(biāo)*/)
                return i - t_len
            else /*匹配中斷*/
                j = next(j match {
                    case 0 => i = i + 1; j/*無“前-后綴”，直接將i下標(biāo)加一匹配*/
                    case _ => j - 1
                })

        }
        -1   /*無匹配項*/
    }

上述代碼缺少\init-next` `函數(shù)的實現(xiàn)，也就是next數(shù)組的獲?。?br> 實際上，next數(shù)組記錄的是模式串T的各個字串C[0 ... j] (0 < j < T.length)的最長“前-后綴”長度信息。
傳統(tǒng)暴力求解next數(shù)組顯然很低效，這里也運(yùn)用KMP匹配的方法獲取next數(shù)組。也就是在模式串T自身上使用KMP匹配：
用兩個變量i和j掃描T，i將模式串看做S，j將模式串看做T。每次增加i時，賦予next[i]合適的值，也就是最長“前-后綴”的長度。

    def `init-next` (s: String): Array[Int] = {
        val len = s.length
        val next = new Array[Int](len)

        next(0) = 0 //首個元素最大前后綴元素：無，所以此處設(shè)置為0
        var i = 1
        var j = 0

        while (i < len) {
            if (s.charAt(i) == s.charAt(j)) {
                j = j + 1
                next(i) = j
                i = i + 1
            } else if (j == 0) {
                next(i) = j
                i = i + 1
            } else {
                j = next(j - 1)
            }
        }
        next
    }