一次在文字裡找「一大堆關鍵字」。它是把 KMP 的失敗函數,搬到 Trie 上的多模式版本。
O(文字長 + 所有模式總長 + 命中數)。它就是「Trie 版的 KMP」—— fail 指標正是 KMP 失敗函數在樹上的推廣。關鍵字過濾、敏感詞偵測、防毒掃描都靠它。
1. 把所有模式掛成 Trie —— 每個關鍵字是一條從根往下的路徑,共用的前綴自動合併(跟字典樹一樣)。到達某模式結尾的節點,記下「這裡是 XX 的結尾」。
2. fail 指標 = 失敗時退到哪 —— 節點 u(代表某個前綴)的 fail[u],指向「u 這個字串的最長真後綴、而且它也是 Trie 裡某條路徑」的那個節點。跟 KMP 的失敗函數一模一樣,只是從一條線變成一棵樹。
3. 用 BFS 逐層接 fail —— 根的孩子 fail 都指向根;其他節點 fail[子] = goto(fail[父], 邊上的字)(沿父親的 fail 找有這條邊的祖先)。一層一層算,前一層算好才算下一層。
4. output link:順著 fail 撿順便命中的模式 —— 若 fail[u] 本身是某模式的結尾,那走到 u 時也同時命中那個模式(例如比對到 she,順便命中 he)。
從根開始,一個字一個字讀 —— 目前狀態在某個 Trie 節點。
有邊就走(goto) —— 目前節點若有這個字的邊,直接走過去。
沒邊就沿 fail 退 —— 走不動時,退到 fail 再試,直到能走、或退回根。文字指標從不回頭(跟 KMP 一樣,i 只前進)。
每到一個節點,報出它(及 output link)的所有命中 —— 一趟掃完,所有關鍵字的所有出現位置全找到。
文章裡同時掃「這幾百個敏感詞有沒有出現」,掃一遍就好,不用一個詞掃一遍。
掃一個檔案,同時比對病毒庫裡上萬條特徵碼 —— AC 自動機是經典做法。
fail 指標像「這條斷了,最近的替代路口在哪」,直接退到那裡繼續,不用從頭重走。
模式 he、she、hers 掛成 Trie(綠圈=某模式結尾)。切「建 fail 指標」看 BFS 怎麼逐節點接 fail(虛線);切「比對 ushers」看狀態怎麼走邊、走不動就退 fail、命中就報。紫色=目前處理的節點 / 狀態。按「下一步」。
從建 Trie、BFS 建 fail、完整 AC 比對,到 output link、單模式退化成 KMP、統計次數,再到複雜度、敏感詞過濾、對照與小結。
❌ 忘了繼承 output link —— out[v] 要接上 out[fail[v]],否則像 she 裡的 he 這種「藏在後綴的命中」會漏掉。
❌ fail 指標算的順序錯 —— 一定要 BFS 由淺到深算,因為 fail[子] 依賴 fail[父](較淺的節點)。用 DFS 會拿到還沒算好的 fail。
❌ 比對時文字指標回頭 —— 走不動只退狀態(沿 fail),文字位置 i 只前進、不回頭(跟 KMP 一樣),這正是線性的關鍵。
❌ 只有一個模式還大費周章 —— 單模式直接用 KMP(第 28 頁)就好,AC 是為「多模式」而生。
ushers 總共命中哪些模式?為什麼讀到 e(she)時,會同時命中 he?r 時,狀態在 she 卻沒有 r 邊,它是怎麼靠 fail 找到 her 的?把答案打到對話裡,我幫你對。