KMP（Knuth-Morris-Pratt）

前言

下面我将按这个目录来介绍 KMP 算法：

字符串『前綴』|『後綴』 PMT(Partial Match Table)『最長公共前後綴』 Next 表 KMP 算法描述 KMP 程式

一、字符串『前綴』|『後綴』

KPM 其實是一種字符串匹配的算法，也就是說檢索字符串，那麼在學習它之前先了解一下『前綴』和『後綴』這 2 個概念。

1. 字符串『前綴』

a. 简单的解释 聲明 2 個字符串: A 和 B 定義它們的關係: A = BS (S 为任意的非空字符) 那麼就稱: B 是 A 的前缀

b. 舉例來看 現在有一個字符串：Hello 那麼它的前綴有：H, He, Hel, Hell

那麼把這個結果更結構化的表達一下： "Hello" = { "H", "He", "Hel", "Hell" }

{} 這裡我們稱它為集合 => 字符串前綴集合

2. 字符串『后綴』

a. 简单的解释 聲明 2 個字符串: A 和 B 定義它們的關係: A = SB (S 为任意的非空字符) 那麼就稱: B 是 A 的后缀

b. 舉例來看 現在有一個字符串：Hello 那麼它的后綴有：ello, llo, lo, o

那麼把這個結果更結構化的表達一下： "Hello" = { "ello", "llo", "lo", "o" }

{} 這裡我們稱它為集合 => 字符串后綴集合

其实这个概念还是挺简单的，我这里参考的是知乎的一个回答来解释一些概念，也许不严谨，但是我认为是易懂的。

不過按我查詢資料來理解 KMP 的時候，有外鏈最先不要跳躍出去，這樣保持一個思維來理解。

接下來將再看一個概念『最長公共前綴』，這個概念才是真正我們編程的時候需要尋找的部分。

二、PMT(Partial Match Table)『最長公共前後綴』

a. 解释和推导

這個概念用文字其實不是那麼好理解，如果硬要用漢字理解的話，就用拆字的方式：最長、公共、前綴、後綴，就是首先要找前綴和後綴，並且要是公共的，並且公共字符串的長度要是最長。

其實我覺得這個漢字解釋是錯的，既然那麼不好解釋，我們就用數學的方式來解釋看看，比較代數式的抽象度更高，更容易看懂。

前提：有一個字符串 $ P_j $ 目的：查找 $ P_j $ 中最長且相等的 k 前缀和 k 後綴

即：滿足條件的最大 k 值，使得，

$ P_0P_1P2...P{k-1}Pk = P{j-k}P{j-k+1}...P{j-2}P_{j-1}P{j} $

这样解释应该比较清晰了，当然这个东西也不是我自己写的，来自于算法老师 July CSDN 中的推导简化的。

b. 实例

模式串: abaabcaba

字符串 前綴 後綴 最长公共字符串 最長公共字符串長度 a 空 空 空 0 ab a b 空 0 aba ab ba a 1 abaab abaa baab ab 2 abaabc abaab baabc 空 0 abaabca abaabc baabca a 1 abaabcab abaabca baabcab ab 2 abaabcaba abaabcab baabcaba aba 3

根据上面的分析表，得出最终的表：

模式串 a b a a b c a b a 最大前缀后缀公共元素长度 0 0 1 1 2 0 1 2 3

c. 为什么需要 PMT？

看完這裡應該有個疑問：為什麼是這個步驟找出這樣一張表出來？這個就需要先了解一下由 PMT 表產生的 Next 表。下面我們先來看看 Next 表的相關東西。

三、Next 表

Next 表是由 PMT 表得到的，做到就是將 PMT 表中的每一個值向后移动 1 位，第一位賦值為 -1，為什麼是這樣得到 Next 表呢？接著看下去吧。

先按結論補充一下之前的表格，添加 Next 表

模式串 a b a a b c a b a 最大前缀后缀公共元素长度 0 0 1 1 2 0 1 2 3 Next -1 0 0 1 1 2 0 1 2

下面這張圖能很好的解釋為什麼我們需要 PMT 得到的 Next 表，這個表意味著我們能夠跳過一些不必要的字符，通過推斷的結構根據 Next 表的數據跳到已經確定的下一個比較位置，這里的 k 就是最長公共子綴的位置。

當我們在進行比較的時候，其實最後的『失配字符』（匹配失敗的字符）是 $ P_k $，所以真正相同的字符串是 $ P_0P1...P{k-1} $，那么我们能得到下面这个公式：

模式串向右移動的位數 := 已匹配字符數 - 失配字符的上一位字符所對應的最大長度值

模式串向右移動的位數 := j - next[j]

这个公式的解释依然出自于 July 的 CSDN 博客 。

以下是文字版公式：

$ S_0S1 \qquad\qquad\qquad\qquad S{i-k}S{i-k+1}...S{i-1} \quad S_i \$ $ \qquad P_0P1...P{k-1}Pk...P{j-k}P{j-k+1}...P{j-1} \quad P_j \$ $ \qquad\qquad\qquad\qquad\qquad P_0 \quad P1 \quad\ ...P{k-1} \quad\ PkP{j-k}P{j-k+1}...P{j-1}P_j $

這裡就能看出 KMP 的优势的，比如暴力的字符串匹配过程是需要每个字符都循环遍历进行比较的，如果遇到不匹配的时候总是移动一位然后再进行比较的过程。而 KMP 是可以跳跃一些不必要的匹配步骤的，时间就节约在这个地方，等會兒後面會分析一下最差情況的時間複雜度。

那么这里描述一下暴力匹配字符串的过程，有這麼 2 個字符串：

匹配串T: ababababab abaabcaba
模式串P: abaabcaba

這個很簡單，直接上代碼吧~因為要對比理解才能看出 KMP 節約的地方：

def index(source_string, type_string, pos):
    i = pos 
    j = 0

    while i <= len(source_string) - 1 and j <= len(type_string) - 1:
        if source_string[i] == type_string[j]:
            i += 1
            j += 1
        else:
            i = i - j + 1
            j = 0

    if j == len(type_string):
        return i - len(type_string)
    else:
        return -1

" output: 8 "
print index("abababababca", "abca", 0)

這個代碼也是參考的博客，python 的程式很直觀，就不翻譯成 JavaScript了。

四、KMP 算法描述

上面的準備工作已經差不多了，現在我們根據上面的 Next 表來描述一下算法過程：

如果 j = -1, 或者當前字符匹配成功(即S[i] == P[j])，都令 i++, j++，继续依次进行比较； 如果 j != -1, 且当前字符匹配失败(即S[i] != P[j])，令 i 不变，j = Next[j]。这个时候就要涉及到按照之前的公式进行移动，移动的位数为：j - Next[j]。

从上面的过程可以看出，我们算法是在解决 $ P_j $ 失配时候的问题。那麼這裡就是我們推斷算法複雜度的地方，算法最差的情況是模式串（P）在 i - j 的位置匹配完成，那么按匹配串（S）來看複雜度就是 O(n)，如果算上 Next 表的過程 O(m)，最後整體的算法複雜度為：O(n+m)。

五、KMP 程式

經過前面那麼多文字和公式的鋪墊，其實實現最後的程式并不複雜，程式包括 2 部分：

總的 KMP 算法實現過程 Next 表的收集

Next 表的收集是有優化的地方的，優化點將以後再分享，這裡先實現它。

下面的 i 表示後綴索引，j 表示前綴索引。

def get_next_table(P):
    i = 0
    j = -1
    next_table = [-1]

    while i < len(P) - 1:
        if j == -1 or P[i] == P[j]:
            i += 1
            j += 1
            next_table.insert(i, j)
        else:
            j = next_table[j]

    return next_table

def index_kmp(S, P, pos):
    next_table = get_next_table(P)
    print next_table
    i = pos
    j = 0

    while i <= len(S) -1 and j <= len(P) - 1:
        if j == -1 or S[i] == P[j]:
            i += 1
            j += 1
        else:
            j = next_table[j]

    if j == len(P):
        return i - j
    else:
        return -1

"""
next_table: [-1, 0, 0, 1, 2, 3, 4, 0]
return: 2
"""
print index_kmp("ababababca", "abababca", 0)

這裡的程式也是參考的網上的一篇文章

参考的太多了，贴一些列表吧：

algorithmen-kmpen 从头到尾彻底理解KMP 从有限状态机的角度去理解Knuth-Morris-Pratt Algorithm(又叫KMP算法) 字符串的匹配模式算法 如何更好的理解和掌握 KMP 算法 Matrix67-KMP算法详解

這篇先這樣吧，之後再寫一些優化和自動機相關的內容呢。