KMP 字串比對：失敗時不從頭來

暴力比對的問題

要在文章 text = "ABABCABAB" 中找 pattern = "ABAB"。

暴力法：

對齊 text[0]，逐字比 ABAB vs ABAB → 比 4 次成功
對齊 text[1]，逐字比 ABAB vs BABC → 第 1 字就失敗
對齊 text[2]，逐字比 ABAB vs ABCA → 第 3 字失敗
…

最壞 O(n × m)——text 長 n、pattern 長 m。

KMP 的洞察：別浪費已配對的部分

當你在 ABABCABAB 找 ABAB，比到 ABAB 配對 ABAB? 第 5 字失敗時—— 前 4 個字 ABAB 你已經知道了！沒必要從第 2 個字 B 重比。

KMP 利用「pattern 自己的前綴 = 後綴」關係，配對失敗時直接跳過已知會匹配的部分。

核心工具：Failure Function（LPS Array）

對 pattern 預先算出一個陣列 lps[i]： lps[i] = pattern[0..i] 中「最長的真前綴 = 真後綴」長度。

例：pattern = ABABAC

i	pattern[0..i]	最長前綴=後綴	lps[i]
0	A	(沒有真前綴)	0
1	AB	沒匹配	0
2	ABA	”A”	1
3	ABAB	”AB”	2
4	ABABA	”ABA”	3
5	ABABAC	(C 結尾的全不匹配)	0

意義：配對到 pattern[i] 失敗時，可以跳到 pattern[lps[i-1]] 繼續比，而不是從 pattern[0] 重來。

跑一遍配對

text = ABABCABAB、pattern = ABAB（lps = [0, 0, 1, 2]）

Step 1: 對齊 text[0..3]
  text:    A B A B C A B A B
  pattern: A B A B
           ↑ ↑ ↑ ↑   (全配對！？)
  
  到 text[3] = B，pattern[3] = B → 配對。pattern 配完了！
  
  記下 match 位置 = 0
  下一步：跳到 lps[3] = 2，pattern 從 index 2 繼續

Step 2: 對齊變成 text[2..]，pattern 從 index 2
  text:    A B A B C A B A B
                 ↓
  pattern:     A B A B
                 ↑
  text[4] = C, pattern[2] = A → 失敗
  
  跳到 lps[1] = 0
  
Step 3: text[4] = C, pattern[0] = A → 失敗
  text 往後一格
  
Step 4: text[5] = A, pattern[0] = A → 配
  text[6] = B, pattern[1] = B → 配
  text[7] = A, pattern[2] = A → 配
  text[8] = B, pattern[3] = B → 配 → match！位置 5

整個過程 text 只被掃一遍，沒有「退回去」重新比。

Pseudocode

Algorithm ComputeLPS(pattern, m):

lps[0] ← 0; len ← 0; i ← 1

while i < m:

if pattern[i] == pattern[len]:

len ← len + 1; lps[i] ← len; i ← i + 1

else if len > 0:

len ← lps[len - 1] // 回退

else:

lps[i] ← 0; i ← i + 1

Algorithm KMP(text, pattern):

lps ← ComputeLPS(pattern, m)

i ← 0; j ← 0 // i 走 text、j 走 pattern

while i < n:

if text[i] == pattern[j]:

i ← i + 1; j ← j + 1

if j == m: report match at i - j; j ← lps[j - 1]

else if j > 0: j ← lps[j - 1] // 跳！不退 i

else: i ← i + 1

複雜度

	Big-O
預處理 LPS	O(m)
配對	O(n)
總計	O(n + m)

比暴力 O(nm) 好太多。當 m=1000、n=10⁶，暴力跑 10⁹，KMP 跑 10⁶。

💡為什麼 i 不會退回？

這是 KMP 的關鍵——text 指標 i 永遠往前，從不回頭。只有 pattern 指標 j 會利用 lps 跳。所以 text 最多被走 n 次 → O(n)。

算 LPS 的小技巧

考試最容易考的就是「給 pattern，求 LPS」。

訣竅：用兩個指標 len 和 i，逐字檢查 pattern[i] 是否等於 pattern[len]。

等：lps[i] = len+1，兩個都往前
不等且 len > 0：len 跳到 lps[len-1] 重試
不等且 len = 0：lps[i] = 0，i 往前

實際算一次 pattern = AABAACAABAA：

i	char	len	動作	lps
0	A	0	初始	[0]
1	A	0→1	pattern[1]=A == pattern[0]=A	[0,1]
2	B	1→0(len=lps[0])→0	pattern[2]≠pattern[1], len=0	[0,1,0]
3	A	0→1	pattern[3]=A == pattern[0]	[0,1,0,1]
4	A	1→2	pattern[4]=A == pattern[1]=A	[0,1,0,1,2]
5	C	2→lps[1]=1→lps[0]=0→0	一路退到 0	[0,1,0,1,2,0]
6	A	0→1		[0,1,0,1,2,0,1]
7	A	1→2		[0,1,0,1,2,0,1,2]
8	B	2→lps[1]=1→ pattern[8]=B == pattern[1]? No → lps[0]=0 → no→0	hmm	(考試會列出詳細狀態)

LPS = [0,1,0,1,2,0,1,2,2,3,4]

📝考試會這樣考

題型一：給 pattern 求 LPS 陣列。 最常考。畫表格，逐 i 列出 len、動作、lps[i]。

題型二：跑一遍 KMP 配對。 給 text、pattern、lps，列出每步的 i, j 變化和配對結果。

題型三：為什麼 KMP 是 O(n + m)？ 答：i 永遠 +1 不退，所以 text 最多走 n 次。 j 退回時是用 lps 跳（每次 j 減少 ≥ 1），總共增加 n 次（隨 i），所以減少也最多 n 次。

題型四：lps[i] 的精確定義？ 最長的「真前綴 = 真後綴」長度——真前綴/後綴不能等於整個字串本身。

這章記住

KMP 用 LPS 表，配對失敗時 pattern 跳但 text 不退。
lps[i] = pattern[0..i] 的最長真前綴 = 真後綴長度。
預處理 O(m) + 配對 O(n) = O(n+m)。
比暴力 O(nm) 快非常多，現代 grep / 搜尋引擎都用類似技巧。