KMP, Knuth-Morris-Pratt
KMP 是字串匹配演算法。
核心做法是先建立 LPS（Longest Prefix Suffix）陣列，
在 mismatch 時避免回頭重複比較。
為什麼 KMP 比暴力法快
暴力法在 mismatch 時，主字串指標常需要回退或重複掃描。
KMP 透過 LPS 知道：
- pattern 目前已匹配的一段中，
- 有多少前綴可以直接當作下一輪的起點。
因此主字串索引 i 不回退，整體可達線性時間。
LPS 是什麼
lps[j] 表示：
在 pattern[0..j] 這段字串中，
「最長相等的真前綴與真後綴」的長度。
例：pattern = "ABABCABAB"
lps = [0,0,1,2,0,1,2,3,4]
Matching 流程（概念）
i指向 textj指向 pattern
- 若
text[i] == pattern[j]，兩者都前進 - 若 mismatch 且
j > 0，令j = lps[j-1] - 若 mismatch 且
j == 0，只前進i - 若
j == len(pattern)，找到一個匹配位置，之後j = lps[j-1]繼續找下一個
Python 範例
def build_lps(pattern: str):
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length > 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
def kmp_search(text: str, pattern: str):
if not pattern:
return [0]
lps = build_lps(pattern)
i = j = 0
ans = []
while i < len(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
ans.append(i - j)
j = lps[j - 1]
elif j > 0:
j = lps[j - 1]
else:
i += 1
return ans
print(kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))
[10]
複雜度
- 建立 LPS：
O(m) - 匹配搜尋：
O(n) - 總計：
O(n + m)
其中：
n= text 長度m= pattern 長度
常見錯誤
- mismatch 時把
j直接歸零（會失去 KMP 優勢） - 忘記
j = lps[j-1]以支援「重疊匹配」 - 空 pattern 的邊界條件未處理