Knuth-Morris-Pratt(KMP) 演算法簡介

Created: November-22, 2018

假設我們有一個文字和一個模式。我們需要確定文字中是否存在模式。例如：

+-------+---+---+---+---+---+---+---+---+
| `Index` | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+---+---+---+---+---+---+---+---+
|  Text | a | b | c | b | c | g | l | x |
+-------+---+---+---+---+---+---+---+---+

+---------+---+---+---+---+
| `Index`   | 0 | 1 | 2 | 3 |
+---------+---+---+---+---+
| `Pattern` | b | c | g | l |
+---------+---+---+---+---+

這種模式確實存在於文字中。所以我們的子字串搜尋應該返回 3 ，即該模式開始的位置的索引。那麼我們的強力子搜尋程式如何工作呢？

我們通常做的是：我們從一開始第 0 中的索引文字和第 0 我們*模式的指數，我們比較文字[0] 與圖案[0] 。由於它們不匹配，我們轉到文字的下一個索引，我們將 Text [1] 與 Pattern [0]進行比較。由於這是匹配，我們也增加模式的索引和文字的索引。我們將 Text [2] 與 Pattern [1]進行比較。他們也是一個匹配。按照之前說明的相同程式，我們現在將 Text [3] 與 Pattern [2]進行比較。由於它們不匹配，我們從下一個開始尋找匹配的位置開始。這是指數 2 中的文字。我們將 Text [2] 與 Pattern [0]進行比較。他們不匹配。然後遞增 Text 的索引，我們將 Text [3] 與 Pattern [0]進行比較。他們相配。再次 Text [4] 和 Pattern [1] 匹配， Text [5] 和 Pattern [2] 匹配， Text [6] 和 Pattern [3] 匹配。由於我們已經到達模式的末尾，我們現在返回匹配開始的索引，即 3 。如果我們的模式是：bcgll，這意味著如果我們的文字中不存在模式，我們的搜尋應該返回異常或 -1 或任何其他預定義的值。我們可以清楚地看到，在最壞的情況下，這種演算法將採取 O(mn) 時間，其中米是長度的文字和 ñ 是的長度模式。我們如何減少這種時間複雜性？這就是 KMP 子字串搜尋演算法進入圖片的地方。 ** **** **** ** **

該克努特莫里斯普拉特的字串搜尋演算法或 KMP 演算法採用的是，當不匹配時，這個詞本身就體現了足夠的資訊，以確定下一個匹配就可以開始觀察搜尋主文字中的模式的出現因此繞過了對先前匹配的字元的重新檢查。該演算法由 Donuld Knuth和 Vaughan Pratt於 1970 年構思，由 James H. Morris獨立構思。三人於 1977 年聯合出版。

讓我們擴充套件我們的示例 Text 和 Pattern 以便更好地理解：

+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| `Index` |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|13|14|15|16|17|18|19|20|21|22|
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  Text |a |b |c |x |a |b |c |d |a |b |x |a |b |c |d |a |b |c |d |a |b |c |y |
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

+---------+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| `Pattern` | a | b | c | d | a | b | c | y |
+---------+---+---+---+---+---+---+---+---+

首先，我們的文字和模式匹配到索引 2 。文字[3] 和模式[3] 不匹配。所以我們的目標是不要在本文中倒退，也就是說，如果不匹配，我們不希望我們的匹配從我們開始匹配的位置再次開始。為了實現這一點，我們將在我們的不匹配發生之前在我們的模式中尋找一個字尾（substring abc ），它也是我們模式的子字串的字首 ** **** **** ** 。對於我們的示例，由於所有字元都是唯一的，因此沒有字尾，即匹配的子字串的字首。那意味著什麼，我們的下一個比較將從索引 0 開始。堅持一下，你會理解為什麼我們這樣做。接下來，我們將 Text [3] 與 Pattern [0]進行比較，但它不匹配。之後，對於從索引 4 到索引 9 的 Text 以及從索引 0 到索引 5 的 Pattern ，我們找到匹配。我們發現 Text [10] 和 Pattern [6]中存在不匹配。所以我們從 Pattern 獲取子字串 **** **** ** **** **** **** **** ** 在發生不匹配的點之前（substring abcdabc ），我們檢查字尾，這也是該子字串的字首。我們可以看到這裡 ab 是這個子字串的字尾和字首。這意味著，因為我們匹配到文字[10] ，不匹配之前的字元是 ab 。我們可以從中推斷出，因為 ab 也是我們所採用的子字串的字首，所以我們不必再次檢查 ab ，下一次檢查可以從 Text [10] 和 Pattern [2]開始。我們沒有回頭看整個文字，我們可以直接從我們的不匹配發生的地方開始。現在我們檢查文字[10] 和模式[2] ，因為它不匹配，並且不匹配前的子字串（ abc ）不包含字尾也是字首，我們檢查 Text [10] 和 Pattern [0] ，它們不要’匹配。之後，對於文字從索引 11 到索引 17 和用於模式從索引 0 至索引 6 。我們在 Text [18] 和 Pattern [7]中發現不匹配。所以我們再次檢查不匹配之前的子字串（substring abcdabc ），並且發現 abc 既是字尾又是字首。因為我們匹配到了模式[7] ， abc 必須在 Text [18] 之前。這意味著，我們不需要比較文字[17] ，我們的比較將從文字[18] 和模式[3]開始。因此我們將找到一個匹配，我們將返回 15 ，這是我們的匹配的起始索引。這就是我們的 KMP 子字串搜尋如何使用字尾和字首資訊。

現在，我們如何有效地計算 if 字尾是否與字首相同以及在什麼時候開始檢查 Text 和 Pattern 之間是否存在不匹配的字元。我們來看一個例子：

+---------+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| `Pattern` | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+

我們將生成一個包含所需資訊的陣列。讓我們把陣列S。陣列的大小將與模式的長度相同。由於 Pattern 的第一個字母不能是任何字首的字尾，我們將 S [0] = 0 。我們首先採用 i = 1 和 j = 0 。在每一步，我們比較 Pattern [i] 和 Pattern [j] 並增加 i 。如果匹配，我們將 S [i] = j + 1 並增加 j ，如果存在不匹配，我們檢查 j 的前一個值位置（如果可用）並設定 j = S [j-1] （如果 j 不等於 0 ），我們一直這樣做，直到 S [j] 沒有’ t 與 S [i] 匹配或 j 不變為 0 。對於後者，我們把 S [i] = 0 。對於我們的例子：

            j   i
+---------+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| `Pattern` | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+

模式[j] 和模式[i] 不匹配，所以我們遞增 i ，因為 j 是 0 ，我們不檢查前一個值並將 Pattern [i] = 0 。如果我們繼續增加 i ，對於 i = 4 ，我們將獲得匹配，因此我們將 S [i] = S [4] = j + 1 = 0 + 1 = 1 並且增加 j 和 i 。我們的陣列看起來像：

                j               i
+---------+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| `Pattern` | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
|    S    | 0 | 0 | 0 | 0 | 1 |   |   |   |
+---------+---+---+---+---+---+---+---+---+

由於 Pattern [1] 和 Pattern [5] 是匹配，我們把 S [i] = S [5] = j + 1 = 1 + 1 = 2 。如果我們繼續，我們會發現 j = 3 和 i = 7 不匹配。由於 j 不等於 0 ，我們把 j = S [j-1] 。我們將比較 i 和 j 上的字元是否相同，因為它們是相同的，我們將把 S [i] = j + 1.我們完成的陣列將如下所示：

+---------+---+---+---+---+---+---+---+---+
|    S    | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+

這是我們需要的陣列。這裡 S [i] 的非零值意味著有一個 S [i] 長度字尾與該子字串中的字首相同（子字串從 0 到 i ），下一個比較將從 S [i] + 1 位置開始。模式。我們生成陣列的演算法如下：

Procedure GenerateSuffixArray(Pattern):
i := 1
j := 0
n := Pattern.length
while i is less than n
    if Pattern[i] is equal to Pattern[j]
        S[i] := j + 1
        j := j + 1
        i := i + 1
    else
        if j is not equal to 0
            j := S[j-1]
        else
            S[i] := 0
            i := i + 1
        end if
    end if
end while

構建這個陣列的時間複雜度是 O(n)，空間複雜度也是 O(n)。為了確保你是否已完全理解該演算法，請嘗試為模式 aabaabaa 生成一個陣列，並檢查結果是否與此匹配。

現在讓我們使用以下示例進行子字串搜尋：

+---------+---+---+---+---+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
|   Text  | a | b | x | a | b | c | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+

+---------+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 |
+---------+---+---+---+---+---+---+
| `Pattern` | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+
|    S    | 0 | 0 | 0 | 1 | 2 | 0 |
+---------+---+---+---+---+---+---+

我們使用之前定義的邏輯有一個 Text ，一個 Pattern 和一個預先計算的陣列 S. 我們比較 Text [0] 和 Pattern [0] ，它們是相同的。文字[1] 和模式[1] 是相同的。文字[2] 和模式[2] 不相同。我們檢查不匹配之前的位置的值。由於 S [1] 為 0 ，因此沒有字尾與我們的子字串中的字首相同，我們的比較從位置 S [1]開始，即 0 。因此 Pattern [0] 與 Text [2]不同所以我們繼續前進。文字[3] 與模式[0] 相同，並且匹配到文字[8] 和模式[5] 。我們在 S 陣列中退後一步，找到 2 。所以這意味著有一個長度為 2 的字首，它也是這個子字串（ abcab） 的字尾，即 ab 。這也意味著在 Text [8] 之前有一個 ab 。因此我們可以安全地忽略 Pattern [0] 和 Pattern [1] 並從 Pattern [2] 和 Text [8] 開始我們的下一次比較。如果我們繼續，我們會找到 **** **** **** **** **** 模式的文字。我們的程式如下：

Procedure KMP(Text, Pattern)
GenerateSuffixArray(Pattern)
m := Text.Length
n := Pattern.Length
i := 0
j := 0
while i is less than m
    if Pattern[j] is equal to Text[i]
        j := j + 1
        i := i + 1
    if j is equal to n
        Return (j-i)
    else if i < m and Pattern[j] is not equal t Text[i]
        if j is not equal to 0
            j = S[j-1]
        else
            i := i + 1
        end if
    end if
end while
Return -1

除了字尾陣列計算之外，該演算法的時間複雜度是 O(m)。由於 GenerateSuffixArray 採用 O(n)，因此 KMP 演算法的總時間複雜度為：O(m+n)。

PS：如果要在文字中找到多次出現的 Pattern ，而不是返回值，請將其列印/儲存並設定 j := S[j-1]。還要保留一個 flag 來跟蹤你是否發現了任何事件，並相應地處理它。 **