在文字裡找樣式。不合時「不整個回頭」,靠失敗函數跳過已比對的,O(n+m)。
O(n·m)。KMP 的聰明處:比對失敗時,文字指標絕不往回走,而是查一張預先算好的失敗函數(LPS 表),讓樣式指標跳到「還能接上的位置」,重用剛剛已配對好的前綴。整體 O(n+m)。
笨方法的浪費 —— 比到一半不合,就把 P 右移一格從頭重比,把「已經配對成功的資訊」全丟掉。
KMP 的洞察 —— 已配對的那段 P[0..j-1],它的「最長相同前後綴」可以直接接上,不用重比。
失敗函數 LPS —— lps[i] = P[0..i] 的「最長真前綴 = 後綴」的長度。這張表只跟 P 有關,先算好。
文字指標 i 不回頭 —— 只有樣式指標 j 會退到 lps[j-1]。所以 T 只掃一遍 → O(n)。
對樣式每個位置 i 問 —— P[0..i] 這段的「開頭」和「結尾」最多有幾個字元一樣(但不能是整段)?
例如 P = "ABABC" —— lps = [0,0,1,2,0]。到 "ABAB"(index 3)時,前綴 "AB" = 後綴 "AB",長度 2。
用途 —— 比到 P[j] 不合時,代表 P[0..j-1] 已配對;跳到 lps[j-1] 就能讓「那段的最長相同前綴」對齊繼續。
建表也是 O(m) —— 用樣式自己比對自己。
O(m) + 掃文字 O(n),i 不回頭。AAAA…AAB 找 AAB)。in / str.find(底層高度優化),KMP 是理解「線性字串比對」原理的經典。對到一半發現不合,不用整句從頭找,記得「剛剛對上的開頭」還能接上。
前幾個字對上、後面錯了,只要退到「還對得上的最長開頭」繼續,不必從頭喊。
在長鏈裡找一小段,重用已配對的片段加速,不重掃。
在文字 ABABABC 找樣式 ABABC(失敗函數 LPS = [0,0,1,2,0])。綠色是已配對、紅色是不合、紫色是正要比的。看 index 4 不合時,樣式 j 從 4 跳到 2、重用 AB,而 i 不回頭。按「下一步」。
從建失敗函數 LPS、KMP 主流程、找所有位置、笨方法對照,到旋轉字串、最短回文、字串週期等 LPS 的巧用。
❌ 失敗時把 i 也退回去 —— 那就退化成笨方法了。KMP 的關鍵是 i 永不回頭,只退 j。
❌ LPS 定義用錯 —— 是「真前綴」(不含整段)= 後綴的最長長度;含整段就永遠是全長,沒意義。
❌ 找所有位置時配到就 return —— 要繼續找得用 j = lps[j-1] 跳,而不是停。
❌ 為了小字串硬寫 KMP —— 短文字 / 只找一次,內建 find 又快又不易錯。
ABABABC 找 ABABC,在 index 4 比對失敗時,樣式 j 從 4 跳到多少?為什麼可以重用 AB?i「絕不回頭」是它 O(n) 的關鍵?P="AAAA" 的 LPS 是什麼?為什麼笨方法在 AAAA…AAB 找 AAB 會退化成 O(n·m)?把答案打到對話裡,我幫你對。