[演算法] KMP演算法簡介

字串搜尋經常出現在日常生活中，因此優化後的字串搜尋演算法必然是大家所追求的目標，而KMP演算法（Knuth–Morris–Pratt algorithm）便是其中之一。在此整理網路上關於KMP的資料。

符號定義

字串搜尋便是在文字材料（text）中找到一些字詞（pattern）。因此定義T代表要搜索的文章（字串），P則代表使用者要找的字詞。

本文的所有字串都是由零開始的陣列。若P = "ALGORITHM"，則P[1]是L。i和j分別代表T和P的索引。

P[0 ... j]表示包含0但不包含j的字元，在數學上用區間表示即是[0,j)。若P = "ALGORITHM"，則P[2 ... 5] = "GOR"。

暴力法

T和P頭對頭（i = 0、j = 0），一次取一字一一比對。

若T[i] == P[j]，則i++、j++
若T[i] != P[j]，則i = i - j + 1、j = 0

時間複雜度O(mn)，空間複雜度O(1)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
T = ABCDAABCDABD
P = ABCDABD
----------------
1.
T = ABCDAABCDABD
P = ABCDABD
    ^^^^^X

2.
T = ABCDAABCDABD
P =  ABCDABD
     X

3.
T = ABCDAABCDABD
P =   ABCDABD
      X

4.
T = ABCDAABCDABD
P =    ABCDABD
       X

5.
T = ABCDAABCDABD
P =     ABCDABD
        ^X

6.
T = ABCDAABCDABD
P =      ABCDABD
         ^^^^^^#

改良

暴力法的精神便是逐一比對，但事實上不必如此。觀察上方第二至五步，若能一次性將P移動至第五步的位置便能減少挪動次數而增加比對效率，尤其T為長字串時效果更為顯著。

第一步比對失敗時，j = 5。我們發現，可以藉由預先分析P[0 ... 5] = "ABCDA"（從P[0]到第一步比對失敗前的子字串）來決定P要挪動多少。

接下來介紹實現此想法所需的前置作業。

Failure Function

中文簡稱F函數，又稱prefix function、border function。給定一字串，它便會輸出「次長相同前綴後綴（longest proper prefix-suffix）」的長度。一個字串可能有不只一個「相同前綴後綴（prefix-suffix）」，而「最長相同前綴後綴」肯定是字串本身；「次長相同前綴後綴」便可顧名思義。

字串	相同前綴後綴	次長相同前綴後綴	F函數
`ABCDE`	`∅`、`ABCDE`	`∅`	0
`ABCDA`	`∅`、`A`、`ABCDA`	`A`	1
`ABCAB`	`∅`、`AB`、`ABCAB`	`AB`	2
`ABCBA`	`∅`、`A`、`ABCBA`	`A`	1
`AAAAA`	`∅`、`A`、`AA`、`AAA`、`AAAA`、`AAAAA`	`AAAA`	4

部分匹配表

我們為P建立部分匹配表（Partial match table）來決定比對失敗時所要挪動的幅度。在此以P = "ABCDABD"為例。

`j`	0	1	2	3	4	5	6
`P[j]`	A	B	C	D	A	B	D
`next[j]`

當P[0]比對失敗後，必須將P右移才能繼續比對，因此設next[j] = -1。

`j`	0	1	2	3	4	5	6
`P[j]`	A	B	C	D	A	B	D
`next[j]`	-1

在j > 0的情況下，next[j] = F(P[0 ... j])。例如：

next[1] = F(P[0 ... 1]) = F("A") = len("") = 0
next[5] = F(P[0 ... 5]) = F("ABCDA") = len("A") = 1
next[6] = F(P[0 ... 6]) = F("ABCDAB") = len("AB") = 2

`j`	0	1	2	3	4	5	6
`P[j]`	A	B	C	D	A	B	D
`next[j]`	-1	0	0	0	0	1	2

其原理便是：當比對失敗時，部分匹配表使你可以直接從next[j]開始繼續搜尋而避免「挪動、比對、失敗」循環（暴力法第二到四步），便達成減少挪動字數的目的。

接著便利用next[j]來搜尋字串：

若T[i] == P[j]，則i++、j++
若T[i] != P[j]，則j = next[j]
- 若j == -1，則i++、j++

時間複雜度O(m+n)，空間複雜度O(n)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
T = ABCDAABCDABD
P = ABCDABD
----------------
1.
T = ABCDAABCDABD
P = ABCDABD
    ^^^^^X

2.
T = ABCDAABCDABD
P =     ABCDABD
         X

3.
T = ABCDAABCDABD
P =      ABCDABD
         ^^^^^^#

此演算法衍生的另一個優點便是，不用每次都從P[0]開始比較，因為F函數已經保證移動後「次長相同前綴後綴」的前綴部分和T的部分相同，如上方的步驟二。

有文獻稱這種演算法為MP演算法（Morris–Pratt algorithm）。

KMP演算法

觀察上面的演算法，在第一步遇到不匹配的字元P便右移，第二步時P[1]又不等於T[5]，須再右移一次。為了使演算法更優化，這時便要藉由優化next來避免連續挪移。

再以P = "ABCDABD"為例並找出連續挪移的條件。P[0 ... 5] = "ABCDA"的「次長相同前綴後綴」為P[0 ... 1] = P[4 ... 5] = "A"，若P[0 .. 1]和P[4 ... 5]的下一個字元相同（都是'B'），則第一次移動後所比較的字元也會相同（'A' != 'B'），因此P必須再移動一次。

1
2
3
4
5
6
P          = ABCDABD
P[0 ... 5] = ABCDA
             !*  !*
--------------------
'!' => 次長相同前綴後綴
'*' => 次長相同前綴後綴的下一個字元

newNext為next的優化版，以實現「避免連續挪移」。

`j`	0	1	2	3	4	5	6
`P[j]`	A	B	C	D	A	B	D
`next[j]`	-1	0	0	0	0	1	2
`newNext[j]`

定義newNext[0] = -1，原因見上一節。若P[0 ... j]的「次長相同前綴後綴」的前綴和後綴沒有相同的「下一個字元」，則newNext[j] = next[j]。

`j`	0	1	2	3	4	5	6
`P[j]`	A	B	C	D	A	B	D
`next[j]`	-1	0	0	0	0	1	2
`newNext[j]`	-1	0	0	0			2

若有相同的下一個字元，則藉遞迴法使其移動時一次到位，即newNext[j] = newNext[next[j]]。在本例中：

`j`	4	5
`P[0 ... j]`	`ABCD`	`ABCDA`
次長相同前綴後綴的前綴	`P[0 ... 0]`	`P[0 ... 1]`
次長相同前綴後綴的後綴	`P[4 ... 4]`	`P[4 ... 5]`
相同的下一個字元	`A`	`B`
`newNext[j]`	-1	0

註：P[0 ... 4]的次長前綴後綴為空，但其仍有相同的下一個字元。

將newNext[j]填完：

`j`	0	1	2	3	4	5	6
`P[j]`	A	B	C	D	A	B	D
`next[j]`	-1	0	0	0	0	1	2
`newNext[j]`	-1	0	0	0	-1	0	2

接著便利用newNext[j]來搜尋字串，規則同上方的改良版：

若T[i] == P[j]，則i++、j++
若T[i] != P[j]，則j = newNext[j]
- 若j == -1，則i++、j++