← 返回首頁
String Algorithms 字串演算法
Text：
Pattern：
KMP 匹配
逐步執行 KMP
顯示 LPS 陣列
載入範例
Text（文本）
Pattern（模式）
LPS（Longest Proper Prefix Suffix）陣列：
匹配過程
點擊「逐步執行 KMP」查看匹配過程
KMP 演算法
時間複雜度：
O(n + m)
，n = text 長度，m = pattern 長度
核心思想：
利用已匹配資訊，避免回退 text 指針
LPS 陣列：
lps[i] = pattern[0..i] 的最長相等前後綴長度
對比暴力法：
暴力 O(nm)，KMP O(n+m)