第一部分：字串演算法¶
場景：用戶搜尋「機器學習」¶
用戶在搜尋框輸入「機器學習」，按下 Enter。
你的系統要在**數十億個網頁**中，找出所有包含「機器學習」這四個字的頁面。
最直覺的方法：對每個網頁，從頭到尾掃一遍，看有沒有這四個字。
「等等，這樣每個網頁都要掃 \(O(nm)\) 次？太慢了！」
設文本長度 \(n\)，模式長度 \(m\)。暴力法在最壞情況下是 \(O(nm)\)。
當 \(n = 10^6\)（一個網頁）、\(m = 100\)（一個查詢詞組），這還勉強可以。但如果要搜尋的模式很長，或者文本有特殊結構，暴力法會非常慢。
你需要一個**線性時間**的字串匹配演算法。
第 1 題：網頁內容搜尋 - KMP 演算法¶
KMP（Knuth-Morris-Pratt）演算法是字串匹配的經典解法，能在 \(O(n + m)\) 時間內完成匹配。
(a) 暴力法的問題在哪？¶
3 分 ・ 大二
你需要知道：暴力法為什麼慢？浪費了什麼資訊？
題目：
-
寫出暴力字串匹配的虛擬碼
-
分析最壞時間複雜度，並給出一個達到最壞情況的例子
-
觀察下面的匹配過程，指出暴力法「浪費」了什麼資訊
Text: A B A B A B A C A B A B
Pattern: A B A B A C
↑ ↑ ↑ ↑ ↑ ✗ (第 6 位不匹配)
暴力法：回到 Text[1]，Pattern[0] 重新開始
Text: A B A B A B A C A B A B
Pattern: A B A B A C
✗ (第 1 位就不匹配)
提示
- 暴力法每次失敗後，Text 指標回退，Pattern 指標歸零
- 但我們已經知道 Pattern 的前幾個字元長什麼樣...
解答
1. 暴力法虛擬碼：
def brute_force(text, pattern):
n, m = len(text), len(pattern)
for i in range(n - m + 1):
j = 0
while j < m and text[i + j] == pattern[j]:
j += 1
if j == m:
return i # 找到匹配
return -1 # 沒找到
2. 最壞時間複雜度：
\(O(nm)\)
最壞情況例子：
每次都要比較 5 個字元才發現不匹配，然後只移動 1 格。
總比較次數：\((n - m + 1) \times m = O(nm)\)
3. 浪費的資訊：
在第一次匹配中，我們已經知道：
Text[0..4] = "ABABA"（匹配了 5 個字元）Pattern[0..4] = "ABABA"
當 Text[5] ≠ Pattern[5] 時，暴力法回到 Text[1] 重新比較。
但我們**已經知道** Text[1] = 'B'，而 Pattern[0] = 'A'，所以 Text[1] 開頭不可能匹配！
更聰明的做法：利用 Pattern 本身的結構，不回退 Text 指標，只調整 Pattern 指標。
這就是 KMP 的核心思想
KMP 的關鍵洞察：Pattern 的前綴可能等於某個後綴。
例如 ABABA：
- 前綴 ABA = 後綴 ABA（長度 3）
- 前綴 A = 後綴 A（長度 1）
當匹配失敗時，不需要從頭開始。如果已匹配的部分有「前綴 = 後綴」的結構，可以直接跳到那個位置繼續比較。
(b) Prefix Function（失敗函數）¶
4 分 ・ 大三
你需要知道：KMP 的核心是 Prefix Function，它記錄了什麼資訊？
題目：
-
定義 Prefix Function \(\pi[i]\)
-
手算 Pattern =
"ABABAC"的 Prefix Function -
說明當
Pattern[j]匹配失敗時，如何利用 \(\pi\) 決定下一步
提示
- \(\pi[i]\) = Pattern[0..i] 的「最長真前綴 = 真後綴」的長度
- 「真」表示不能是自己本身
解答
1. Prefix Function 定義：
對於 Pattern \(P[0..m-1]\)，定義：
白話文：\(\pi[i]\) 是 \(P[0..i]\) 這個字串中，最長的「真前綴 = 真後綴」 的長度。
2. 手算 "ABABAC"：
| \(i\) | \(P[0..i]\) | 真前綴 = 真後綴 | \(\pi[i]\) |
|---|---|---|---|
| 0 | A |
無（長度 1 沒有真前綴） | 0 |
| 1 | AB |
無 | 0 |
| 2 | ABA |
A = A |
1 |
| 3 | ABAB |
AB = AB |
2 |
| 4 | ABABA |
ABA = ABA |
3 |
| 5 | ABABAC |
無（C 打破了結構） | 0 |
結果：\(\pi = [0, 0, 1, 2, 3, 0]\)
3. 匹配失敗時如何利用 \(\pi\)：
假設我們正在比較 Text[i] 和 Pattern[j]，發現不匹配。
暴力法：\(i \leftarrow i - j + 1\)，\(j \leftarrow 0\)（回退 Text）
KMP：\(j \leftarrow \pi[j-1]\)（不回退 Text！）
為什麼？因為 \(\pi[j-1]\) 告訴我們：Pattern[0..j-1] 的前 \(\pi[j-1]\) 個字元，等於它的後 \(\pi[j-1]\) 個字元。
而這後 \(\pi[j-1]\) 個字元，正是我們剛才在 Text 中匹配過的！所以不需要重新比較。
數學小結：Prefix Function
| 概念 | 說明 |
|---|---|
| \(\pi[i]\) | \(P[0..i]\) 的最長「真前綴 = 真後綴」長度 |
| 計算時間 | \(O(m)\) |
| 用途 | 匹配失敗時，決定 Pattern 指標跳到哪 |
© Prefix Function 的計算¶
4 分 ・ 大三
你需要知道：如何在 \(O(m)\) 時間內計算 Prefix Function？
題目：
-
寫出計算 Prefix Function 的演算法
-
證明時間複雜度是 \(O(m)\)
-
考古題練習：對於 Pattern =
"ABCDABCE"，計算 \(\pi[7]\) 的值（110 Q10）
提示
- 關鍵：\(\pi[i]\) 可以從 \(\pi[i-1]\) 遞推
- 如果 \(P[\pi[i-1]] = P[i]\)，則 \(\pi[i] = \pi[i-1] + 1\)
- 否則，嘗試更短的前綴
解答
1. 計算演算法：
def compute_prefix(pattern):
m = len(pattern)
pi = [0] * m
k = 0 # 當前匹配的前綴長度
for i in range(1, m):
# 當前字元不匹配時，回退到更短的前綴
while k > 0 and pattern[k] != pattern[i]:
k = pi[k - 1]
# 如果匹配，前綴長度 +1
if pattern[k] == pattern[i]:
k += 1
pi[i] = k
return pi
2. 時間複雜度證明：
觀察變數 \(k\)：
- k += 1 最多執行 \(m - 1\) 次（每次 \(i\) 增加 1，\(k\) 最多增加 1）
- k = pi[k-1] 每次至少讓 \(k\) 減少 1
由於 \(k \geq 0\) 且 \(k\) 的增加總量 \(\leq m\)，所以減少的總量也 \(\leq m\)。
因此 while 迴圈的總執行次數 \(\leq m\)。
總時間複雜度：\(O(m)\)
3. 考古題："ABCDABCE"
| \(i\) | \(P[0..i]\) | \(\pi[i]\) |
|---|---|---|
| 0 | A |
0 |
| 1 | AB |
0 |
| 2 | ABC |
0 |
| 3 | ABCD |
0 |
| 4 | ABCDA |
1 |
| 5 | ABCDAB |
2 |
| 6 | ABCDABC |
3 |
| 7 | ABCDABCE |
0 |
答案：\(\pi[7] = 0\)
（因為 ABCDABCE 沒有「真前綴 = 真後綴」，E 打破了結構）
(d) KMP 演算法完整實現¶
3 分 ・ 大二
你需要知道：如何用 Prefix Function 實現線性時間字串匹配？
題目：
-
寫出完整的 KMP 演算法
-
分析時間複雜度
-
手動執行：Text =
"ABABABABAC"，Pattern ="ABABAC"
解答
1. KMP 演算法：
def kmp_search(text, pattern):
n, m = len(text), len(pattern)
if m == 0:
return 0
# 預處理：計算 Prefix Function
pi = compute_prefix(pattern)
# 匹配
j = 0 # Pattern 指標
results = []
for i in range(n): # Text 指標
# 不匹配時，利用 pi 跳轉
while j > 0 and text[i] != pattern[j]:
j = pi[j - 1]
# 匹配時，前進
if text[i] == pattern[j]:
j += 1
# 找到完整匹配
if j == m:
results.append(i - m + 1)
j = pi[j - 1] # 繼續找下一個匹配
return results
2. 時間複雜度：
- 預處理：\(O(m)\)
- 匹配：\(O(n)\)（同樣的分析，\(j\) 的增減總量都是 \(O(n)\)）
總時間：\(O(n + m)\)
3. 手動執行：
Text: A B A B A B A B A C
Pattern: A B A B A C
pi: [0,0,1,2,3,0]
i=0: T[0]=A, P[0]=A, j=1
i=1: T[1]=B, P[1]=B, j=2
i=2: T[2]=A, P[2]=A, j=3
i=3: T[3]=B, P[3]=B, j=4
i=4: T[4]=A, P[4]=A, j=5
i=5: T[5]=B, P[5]=C, 不匹配！j=pi[4]=3
T[5]=B, P[3]=B, j=4
i=6: T[6]=A, P[4]=A, j=5
i=7: T[7]=B, P[5]=C, 不匹配！j=pi[4]=3
T[7]=B, P[3]=B, j=4
i=8: T[8]=A, P[4]=A, j=5
i=9: T[9]=C, P[5]=C, j=6 ✓
找到匹配！位置 = 9 - 6 + 1 = 4
答案：在位置 4 找到匹配
(e) 有限自動機表示¶
4 分 ・ 碩一
你需要知道：KMP 可以用有限自動機（DFA）來理解
題目（改編自 110 Q11）：
給定字串匹配的狀態轉移表：
| 狀態 | A | B | C |
|---|---|---|---|
| 0 | 1 | 0 | 0 |
| 1 | 1 | 2 | 0 |
| 2 | 3 | 0 | 0 |
| 3 | 1 | 4 | 0 |
| 4 | 3 | 0 | 5 |
| 5 | (接受) |
-
推導出這個 DFA 對應的 Pattern 是什麼
-
解釋狀態轉移和 Prefix Function 的關係
提示
- 狀態 \(i\) 表示「已匹配 Pattern 的前 \(i\) 個字元」
- 轉移 \(\delta(i, c)\) = 「在狀態 \(i\) 遇到字元 \(c\)，下一個狀態是什麼」
解答
1. 推導 Pattern：
從狀態轉移表分析： - 狀態 0 → 1：讀 A（Pattern[0] = A） - 狀態 1 → 2：讀 B（Pattern[1] = B） - 狀態 2 → 3：讀 A（Pattern[2] = A） - 狀態 3 → 4：讀 B（Pattern[3] = B） - 狀態 4 → 5：讀 C（Pattern[4] = C）
Pattern = "ABABC"
驗證一些轉移： - \(\delta(2, A) = 3\)：在狀態 2（已匹配 "AB"），遇到 A，變成狀態 3（已匹配 "ABA"） - \(\delta(4, A) = 3\)：在狀態 4（已匹配 "ABAB"），遇到 A 而非 C。此時已匹配的後綴 "ABA" 是 Pattern 的前綴，所以跳到狀態 3
2. 與 Prefix Function 的關係：
當 \(P[j] \neq c\) 時：
也就是說，DFA 的失敗轉移等價於 KMP 的 \(\pi\) 函數跳轉。
**DFA 版本**需要 \(O(m|\Sigma|)\) 空間（\(|\Sigma|\) = 字母表大小），但查詢時不需要回退。
**KMP 版本**只需要 \(O(m)\) 空間，但每次失敗可能要多次跳轉。
兩者時間複雜度都是 \(O(n + m)\)。
進階挑戰：KMP 執行次數分析¶
4 分 ・ 碩一
考古題（112 Q16）：
對於 KMP 演算法的以下程式碼，計算第 7 行執行次數的最大值。
1 def kmp(text, pattern):
2 pi = compute_prefix(pattern)
3 j = 0
4 for i in range(len(text)):
5 while j > 0 and text[i] != pattern[j]:
6 j = pi[j - 1] # 第 6 行
7 if text[i] == pattern[j]: # 第 7 行
8 j += 1
設 Text 長度 \(n\)，Pattern 長度 \(m\)。
解答
分析：
第 7 行在 for 迴圈內，每次 \(i\) 增加時執行一次。
for 迴圈執行 \(n\) 次，所以**第 7 行最多執行 \(n\) 次**。
這個上界是緊的（tight）：當每個字元都匹配時，第 7 行每次都執行。
答案：\(n\)
（注意：第 6 行的執行次數分析更複雜，需要用到 \(j\) 的增減平衡論證）
第 1 題小結：你的字串匹配工具箱¶
「怎麼快速在網頁中找到關鍵字？」
│
├─► (a) 暴力法太慢
│ → O(nm)，浪費已匹配的資訊
│
├─► (b) 關鍵洞察：Prefix Function
│ → π[i] = 最長「真前綴 = 真後綴」
│ → 匹配失敗時，跳到 π[j-1]
│
├─► (c) 計算 Prefix Function
│ → O(m) 時間
│ → 遞推：從 π[i-1] 推 π[i]
│
├─► (d) KMP 完整演算法
│ → O(n + m) 時間
│ → 永不回退 Text 指標
│
└─► (e) DFA 觀點
→ 狀態 = 已匹配長度
→ 轉移 = 下一個狀態
| 概念 | 重點 |
|---|---|
| 暴力法 | \(O(nm)\)，回退浪費資訊 |
| Prefix Function | \(\pi[i]\) = 最長真前綴=真後綴 |
| KMP | \(O(n+m)\)，利用 \(\pi\) 跳轉 |
| DFA | \(O(m\|\Sigma\|)\) 空間，\(O(n)\) 查詢 |