目錄

  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. 多個測試案例

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