KMP 解決一個 pattern 的問題；AC 自動機解決同一個問題在有幾萬個 pattern 時的版本。
為什麼不用 k 次 KMP？
你要在一篇文章裡找出所有出現的敏感詞，總計有 10 萬個 pattern，文章長度 n = 10^6。
逐個跑 KMP：O(k × n) = 10^11——不可能。
AC 自動機把所有 pattern 組合起來，只掃一遍文本：O(n + Σm + z)，m = 各 pattern 長度，z = 總匹配次數。
三個核心結構
Trie：把所有 pattern 插入字典樹，共享前綴。pattern = [“he”, “she”, “his”, “hers”]：
root
├── h → e → [he] → r → s → [hers]
│ └── i → s → [his]
└── s → h → e → [she]失敗鏈結（Failure Link）：類似 KMP 的失敗函數，但作用在 Trie 節點上。節點 u 的 failLink 指向 u 代表字串的「最長真後綴」在 Trie 中對應的節點。
"she" 末尾節點的 failLink = "he" 末尾節點
（"she" 的最長真後綴 "he" 存在於 Trie 中）匹配失敗時，沿 failLink 回退——不從根重新開始，能繼承前面已匹配的後綴。
輸出鏈結（Output Link）：當某節點不是任何 pattern 的結尾，但沿 failLink 路徑上有結尾節點，輸出鏈結直接指向最近的那個，讓匹配報告更方便。
建構：先插 Trie，再 BFS 補 failLink
第一步就是普通的 Trie 插入——把每個 pattern 一個字元一個字元塞進去，共享前綴，末端節點記下這是第幾個 pattern。這步沒什麼玄機，但少了它下面的 failLink 無枝可掛：
void addPattern(String pattern) {
int cur = 0;
for (char c : pattern.toCharArray()) {
trie[cur].children.putIfAbsent(c, newNode());
cur = trie[cur].children.get(c);
}
trie[cur].patternIdx = patternId++; // 標記：這裡是某個 pattern 的結尾
}真正的難點在第二步——failLink 要用 BFS 一層一層建，因為 u 的 failLink 得先算好，才能推得出它子節點的 failLink：
void buildFailLinks() {
Queue<Integer> queue = new LinkedList<>();
// 根的直接子節點：failLink 指根
for (int child : trie[0].children.values()) {
trie[child].fail = 0;
queue.add(child);
}
while (!queue.isEmpty()) {
int u = queue.poll();
for (var entry : trie[u].children.entrySet()) {
char c = entry.getKey();
int v = entry.getValue();
// v 的 failLink = u 的 failLink 沿著 c 走到的節點
int f = trie[u].fail;
while (f != 0 && !trie[f].children.containsKey(c))
f = trie[f].fail;
trie[v].fail = trie[f].children.getOrDefault(c, 0);
// outputLink：沿 fail 鏈指向「最近一個是 pattern 結尾」的節點，
// 報告時就能一次跳過去，不用整條 fail 鏈慢慢走
trie[v].outputLink = (trie[trie[v].fail].patternIdx != -1)
? trie[v].fail
: trie[trie[v].fail].outputLink;
queue.add(v);
}
}
}搜尋
掃描文本時，當前節點沿字元轉移；若無對應轉移，沿 failLink 回退（等同 KMP 回退）：
void search(String text) {
int cur = 0;
for (int textPos = 0; textPos < text.length(); textPos++) {
char c = text.charAt(textPos);
while (cur != 0 && !trie[cur].children.containsKey(c))
cur = trie[cur].fail;
cur = trie[cur].children.getOrDefault(c, 0);
// 報告所有匹配（沿輸出鏈結）
int tmp = cur;
while (tmp != 0) {
if (trie[tmp].patternIdx != -1)
report(trie[tmp].patternIdx, textPos);
tmp = trie[tmp].outputLink;
}
}
}複雜度：一次建表，掃文本只花一趟
| 步驟 | 時間 | 說明 |
|---|---|---|
| 建 Trie | O(m) | m = 所有 pattern 總長度 |
| 建 failLink | O(m) | BFS 走遍每個節點一次 |
| 搜尋文本 | O(n + z) | n = 文本長度，z = 總匹配次數 |
| 合計 | O(n + m + z) |
跟開頭那個 10 萬 pattern、n = 10^6 的例子對照就有感覺：k 次 KMP 是 O(k × n)，AC 自動機把 k 收進了「建表一次」的 m 裡，文本永遠只掃一趟。pattern 再多，掃描那一趟的成本不變——這才是它能撐敏感詞過濾、病毒碼偵測、DNA 多模式搜尋的原因。
🎬 互動視覺化：Aho-Corasick 自動機動畫 — 看 Trie 長出來、failLink 一條條接上，再餵一段文本進去，游標沿字元轉移、失配時沿 failLink 回退，所有命中的 pattern 同時亮起。
AC 自動機 = Trie + KMP 的失敗函數——如果你懂這兩個結構，AC 自動機只是把它們合在一起。
接下來往哪走
- 組合博弈論：Nim 遊戲與 Sprague-Grundy 定理 — 下一篇：從字串切到博弈論，競程的必修冷門科
- Trie 前綴樹（字典樹） — AC 自動機的骨架，children 和節點結構的基礎
- String Algorithms 字串演算法 — failLink 的原型就是 KMP 的失敗函數，出處在這裡