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 就是最長公共子綴的位置。

"next"

當我們在進行比較的時候,其實最後的『失配字符』(匹配失敗的字符)是 $ 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

"1"

這個很簡單,直接上代碼吧~因為要對比理解才能看出 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算法详解

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

文章来源:

Author:小撸
link:http://www.60sky.com/post/algorithmen-kmpen.html