KMP KnuthMorrisPratt 字串匹配演算法 — 完整教學

---

目錄

1. 問題定義
2. 暴力法（Brute Force）及其缺點
3. KMP 的核心思想
4. 前綴函數（Failure Function / Partial Match Table）
5. 前綴函數的建構過程
6. KMP 搜尋過程
7. 完整手動推演範例
8. 時間與空間複雜度分析
9. KMP 的應用場景
10. 常見變體與延伸
11. C++ 程式碼參照

---

1. 問題定義

字串匹配問題（String Matching / Pattern Search）：

給定一段文字 text（長度 N）和一個模式字串 pattern（長度 M），找出 pattern 在 text 中所有出現的位置。

例子：

text:    "ABABDABACDABABCABAB"
pattern: "ABABCABAB"
答案:    位置 10（0-based: 索引 9）

---

2. 暴力法（Brute Force）及其缺點

2.1 做法

對 text 的每個位置 i = 0, 1, …, N−M，逐字元比對 pattern[0..M-1]。

i = 0: text[0..M-1] vs pattern[0..M-1]
i = 1: text[1..M]   vs pattern[0..M-1]
...

2.2 時間複雜度

• 最壞情況：O(N × M)
• 例如 text = "AAAAAAB"，pattern = "AAAB"，每次比對幾乎成功 M−1 個字元後才失敗，然後只退回一格重新比對。

2.3 問題所在

暴力法在比對失敗時，丟棄了已比對成功的資訊，每次回退只前進 1 格。

text:    A B A B A B C
pattern: A B A B C        ← 比對到 pattern[4] 失敗
         ↑ 暴力法會回到 text[1] 重新開始

但我們已經知道 text[2..3] = "AB" = pattern[0..1]，不必重頭比！

---

3. KMP 的核心思想

KMP 的關鍵洞察：

當比對在 pattern[j] 失敗時，pattern[0..j-1] 已經匹配成功。我們可以利用 pattern 本身的結構（前綴 = 後綴的關係），把 pattern 向右滑動到正確的位置，避免重複比對。

具體來說：

• text 的指標 i 永遠不回退（只前進），每個字元最多被看一次。
• pattern 的指標 j 根據「前綴函數」快速跳到正確位置。

這就是 KMP 能達到 O(N + M) 的原因。

---

4. 前綴函數（Failure Function / Partial Match Table）

4.1 定義

對 pattern[0..M-1]，定義陣列 failure[j]（也叫 lps[j]、next[j]、π[j]）：

failure[j] = pattern[0..j] 的最長「真前綴 = 真後綴」的長度。

• 「真前綴」= 不包含整個字串本身的前綴。
• 「真後綴」= 不包含整個字串本身的後綴。

4.2 例子

j	pattern[0..j]	所有真前綴	所有真後綴	最長相等的	failure[j]
0	A	(無)	(無)	(無)	0
1	AB	A	B	無	0
2	ABA	A, AB	A, BA	"A"	1
3	ABAB	A, AB, ABA	B, AB, BAB	"AB"	2
4	ABABC	A..ABAB	C..BABC	無	0
5	ABABCA	A..ABABC	A..BABCA	"A"	1
6	ABABCAB	A..ABABCA	B..ABCAB	"AB"	2
7	ABABCABA	A..ABABCAB	A..BCABA	"ABA"	3
8	ABABCABAB	A..ABABCABA	B..CABAB	"ABAB"	4

所以 pattern = "ABABCABAB" 的 failure 陣列為：

j:        0  1  2  3  4  5  6  7  8
pattern:  A  B  A  B  C  A  B  A  B
failure:  0  0  1  2  0  1  2  3  4

4.3 failure 的意義

當比對在 pattern[j] 失敗時： - pattern[0..j-1] 已匹配成功。 - failure[j-1] 告訴我們：pattern[0..j-1] 中，有多長的後綴同時也是前綴。 - 因此我們可以把 j 跳到 failure[j-1]，繼續比對，不必回退 text 的指標 i。

text:    ... X X A B A B ? ...
pattern:         A B A B C A B A B
                             ↑ j=4 失敗, failure[3]=2
跳至:            A B A B C A B A B
                     ↑ j=2, 從 pattern[2] 繼續比

---

5. 前綴函數的建構過程

5.1 演算法（自我匹配）

建構 failure 陣列的精髓：把 pattern 和自己做 KMP 匹配。

failure[0] = 0  （單一字元沒有真前綴）

對 i = 1, 2, ..., M-1:
    令 j = failure[i-1]
    while j > 0 且 pattern[i] ≠ pattern[j]:
        j = failure[j-1]   ← 沿著 failure 鏈回退
    if pattern[i] == pattern[j]:
        j = j + 1
    failure[i] = j

5.2 逐步推演（pattern = "ABABCABAB"）

初始: failure = [0, ?, ?, ?, ?, ?, ?, ?, ?]

i=1: pattern[1]='B', j=failure[0]=0, pattern[0]='A'≠'B' → failure[1]=0
     failure = [0, 0, ?, ?, ?, ?, ?, ?, ?]

i=2: pattern[2]='A', j=failure[1]=0, pattern[0]='A'=='A' → j=1 → failure[2]=1
     failure = [0, 0, 1, ?, ?, ?, ?, ?, ?]

i=3: pattern[3]='B', j=failure[2]=1, pattern[1]='B'=='B' → j=2 → failure[3]=2
     failure = [0, 0, 1, 2, ?, ?, ?, ?, ?]

i=4: pattern[4]='C', j=failure[3]=2, pattern[2]='A'≠'C'
     j=failure[1]=0, pattern[0]='A'≠'C' → failure[4]=0
     failure = [0, 0, 1, 2, 0, ?, ?, ?, ?]

i=5: pattern[5]='A', j=failure[4]=0, pattern[0]='A'=='A' → j=1 → failure[5]=1
     failure = [0, 0, 1, 2, 0, 1, ?, ?, ?]

i=6: pattern[6]='B', j=failure[5]=1, pattern[1]='B'=='B' → j=2 → failure[6]=2
     failure = [0, 0, 1, 2, 0, 1, 2, ?, ?]

i=7: pattern[7]='A', j=failure[6]=2, pattern[2]='A'=='A' → j=3 → failure[7]=3
     failure = [0, 0, 1, 2, 0, 1, 2, 3, ?]

i=8: pattern[8]='B', j=failure[7]=3, pattern[3]='B'=='B' → j=4 → failure[8]=4
     failure = [0, 0, 1, 2, 0, 1, 2, 3, 4]

5.3 「沿 failure 鏈回退」的直覺

當 pattern[i] ≠ pattern[j] 時，我們不是回到 j=0 重頭來，而是跳到 failure[j-1]。

為什麼？ 因為 failure[j-1] 表示 pattern[0..j-1] 中第二長的前綴=後綴。如果這個更短的前綴後面的字元能匹配 pattern[i]，我們就找到了 failure[i]。

這個過程可能沿著 failure 鏈跳好幾次（最壞到 j=0），但攤銷分析保證整體 O(M)。

---

6. KMP 搜尋過程

6.1 演算法

j = 0  （pattern 的比對指標）

for i = 0, 1, ..., N-1:     ← text 的指標，永不回退
    while j > 0 且 text[i] ≠ pattern[j]:
        j = failure[j-1]    ← 利用前綴函數跳轉
    if text[i] == pattern[j]:
        j = j + 1
    if j == M:
        輸出 "匹配在位置 i - M + 1"
        j = failure[j-1]    ← 繼續找下一個匹配

6.2 為什麼 i 不回退？

• 若 text[i] == pattern[j]，兩者同步前進。
• 若 text[i] ≠ pattern[j]，只有 j 回退（沿 failure 鏈），i 不動。
• j 的回退不會超過它之前增加的總量（攤銷 O(N)）。

---

7. 完整手動推演範例

text:    A B A B D A B A C D A B A B C A B A B
pattern: A B A B C A B A B
failure: 0 0 1 2 0 1 2 3 4

步驟	i	text[i]	j	pattern[j]	動作
1	0	A	0	A	匹配, i=1, j=1
2	1	B	1	B	匹配, i=2, j=2
3	2	A	2	A	匹配, i=3, j=3
4	3	B	3	B	匹配, i=4, j=4
5	4	D	4	C	不匹配, j=failure[3]=2
6	4	D	2	A	不匹配, j=failure[1]=0
7	4	D	0	A	不匹配, j=0 且不等, i=5
8	5	A	0	A	匹配, i=6, j=1
9	6	B	1	B	匹配, i=7, j=2
10	7	A	2	A	匹配, i=8, j=3
11	8	C	3	B	不匹配, j=failure[2]=1
12	8	C	1	B	不匹配, j=failure[0]=0
13	8	C	0	A	不匹配, i=9
14	9	D	0	A	不匹配, i=10
15	10	A	0	A	匹配, i=11, j=1
16	11	B	1	B	匹配, i=12, j=2
17	12	A	2	A	匹配, i=13, j=3
18	13	B	3	B	匹配, i=14, j=4
19	14	C	4	C	匹配, i=15, j=5
20	15	A	5	A	匹配, i=16, j=6
21	16	B	6	B	匹配, i=17, j=7
22	17	A	7	A	匹配, i=18, j=8
23	18	B	8	B	匹配, j=9==M → 找到！位置 10 (i-M+1=18-9+1=10)
					j=failure[8]=4, 繼續搜尋...

位置:  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
text:  A  B  A  B  D  A  B  A  C  D  A  B  A  B  C  A  B  A  B
                                       [A  B  A  B  C  A  B  A  B]
                                       ↑ 位置 10 (0-based: 索引 10 ─ 但以 0-based 計為 9)

---

8. 時間與空間複雜度分析

8.1 前綴函數建構：O(M)

• 變數 j 在整個過程中：
• 每次 j++ 最多 1 次（每輪 i），所以 j 總共增加 ≤ M 次。
• j = failure[j-1] 使 j 嚴格遞減，j 不會減到負數。
• 因此 while 迴圈中的回退次數總計 ≤ M 次。
• 總時間：O(M)。

8.2 KMP 搜尋：O(N)

• 同理，i 從 0 走到 N−1，j 總增加 ≤ N 次，回退次數總計 ≤ N 次。
• 總時間：O(N)。

8.3 空間：O(M)

• failure 陣列大小 M。

8.4 總計

項目	複雜度
前處理（建 failure）	O(M)
搜尋	O(N)
總時間	O(N + M)
空間	O(M)

比暴力法的 O(NM) 好得多，尤其當 pattern 有大量重複結構時差異最為明顯。

---

9. KMP 的應用場景

應用	說明
文字編輯器的查找/替換	Ctrl+F 搜尋字串
DNA 序列比對	在基因組中找特定基因片段
網路入侵偵測	在封包內容中搜尋惡意特徵碼
編譯器的詞法分析	匹配關鍵字、識別符號
最短重複週期	pattern 的最小週期 = M − failure[M−1]
求字串所有前綴=後綴	沿 failure 鏈回溯即得

---

10. 常見變體與延伸

變體	說明
failure 優化版（failureDD / next 陣列）	當 pattern[failure[j]] == pattern[j] 時，直接跳到 failure[failure[j]]，減少無效比對
多模式匹配：Aho-Corasick	把多個 pattern 建成 Trie + failure 指標，一次掃描 text 即可匹配所有 pattern
Z-algorithm	另一種 O(N+M) 的字串匹配方法，概念不同但效率相同
2D KMP	在二維矩陣中搜尋二維 pattern

---

11. C++ 程式碼參照

配套的完整 C++ 實現請見 kmp_algorithm.cpp，其中包含：

1. 暴力法（Brute Force）— O(NM) 對照用
2. buildFailure() — 建構前綴函數，附逐步 debug 輸出
3. kmpSearch() — KMP 搜尋主體，附逐步 debug 輸出
4. optimized failure — 優化版前綴函數
5. 最短重複週期的計算
6. 多個測試案例

所有函式都有詳盡的中英文註釋，方便逐行理解。