AC 自動機（Aho-Corasick Algorithm）是多模式串匹配的經典演算法，結合 Trie 樹與失敗指標（Failure Link），能在 O(n + m + k) 時間複雜度內（n 為文本長度，m 為模式總長度，k 為匹配次數）完成全文檢索，廣泛應用於敏感詞過濾、關鍵字高亮、入侵偵測等場景。本文提供完整的 Java 實作碼，包含 Trie 節點設計、兩種節點實作（ASCII 優化與通用 Map）、自動機建構與查詢邏輯，並附帶測試示例。
Nodeinterface Node {
char value(); // 節點字元
boolean exists(); // 是否為模式結尾
boolean isRoot(); // 是否為根節點
Node parent(); // 父節點
Node childOf(char c); // 獲取子節點
Node fail(); // 失敗指標
void setFail(Node node); // 設定失敗指標
void setExists(boolean exists); // 標記模式結尾
void add(Node child); // 新增子節點
List<Node> children(); // 所有子節點
}AbstractNode封裝共同欄位與 toString() 視覺化輸出，子類專注於子節點儲存策略。
abstract class AbstractNode implements Node {
private static final char EMPTY = '\0';
private final char value;
private final Node parent;
private boolean exists;
private Node fail;
protected AbstractNode(Node parent, char value) {
this.parent = parent; this.value = value; this.exists = false; this.fail = null;
}
protected AbstractNode() { this(null, EMPTY); }
// ... 介面方法預設實作（getter/setter） ...
@Override public String toString() { return toString(this, 0); }
private static String toString(Node node, int depth) { /* 遞迴產生 XML 格式樹結構 */ }
}AsciiNode針對可列印 ASCII 字元（32~126），使用固定大小陣列 Node[95] 直接索引，O(1) 存取，記憶體效率高。
final class AsciiNode extends AbstractNode {
private static final char FROM = 32, TO = 126;
private final Node[] children = new Node[TO - FROM + 1];
public AsciiNode() { super(); }
public AsciiNode(Node parent, char value) { super(parent, value); }
@Override public Node childOf(char c) {
return (c >= FROM && c <= TO) ? children[c - FROM] : null;
}
@Override public void add(Node child) { children[child.value() - FROM] = child; }
@Override public List<Node> children() { /* 遍歷陣列收集非 null 節點 */ }
}MapNode支援 Unicode（含中文），使用 HashMap 動態儲存子節點。
final class MapNode extends AbstractNode {
private final Map<Character, Node> children = new HashMap<>();
public MapNode() { super(); }
public MapNode(Node parent, char value) { super(parent, value); }
@Override public Node childOf(char c) { return children.get(c); }
@Override public void add(Node child) { children.put(child.value(), child); }
@Override public List<Node> children() { return new ArrayList<>(children.values()); }
}WordTableNodeMakerinterface NodeMaker {
Node make(Node parent, char value);
Node makeRoot();
}public final class WordTable {
private final Node root;
private WordTable(Collection<? extends CharSequence> words, NodeMaker maker) {
this.root = buildTrie(words, maker);
setFailNode(root);
}
public static WordTable compile(Collection<? extends CharSequence> words) {
if (words == null || words.isEmpty()) throw new IllegalArgumentException();
NodeMaker maker = isAscii(words) ? new AsciiMaker() : new MapMaker();
return new WordTable(words, maker);
}
private static boolean isAscii(Collection<? extends CharSequence> words) {
for (CharSequence w : words)
for (int i = 0, len = w.length(); i < len; i++)
if (w.charAt(i) < 32 || w.charAt(i) > 126) return false;
return true;
}
// ... 內部類 AsciiMaker / MapMaker 實作 NodeMaker ...
}buildTrie()private static Node buildTrie(Collection<? extends CharSequence> words, NodeMaker maker) {
Node root = maker.makeRoot();
for (CharSequence seq : words) {
Node cur = root;
for (int i = 0, len = seq.length(); i < len; i++) {
char c = seq.charAt(i);
Node next = cur.childOf(c);
if (next == null) {
next = maker.make(cur, c);
cur.add(next);
}
cur = next;
if (i == len - 1) cur.setExists(true); // 模式結尾標記
}
}
return root;
}setFailNode()private static void setFailNode(Node root) {
root.setFail(null);
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
Node parent = q.poll();
for (Node child : parent.children()) {
if (parent.isRoot()) {
child.setFail(root);
} else {
Node temp = parent.fail();
while (temp != null) {
Node f = temp.childOf(child.value());
if (f != null) { child.setFail(f); break; }
temp = temp.fail();
}
if (temp == null) child.setFail(root);
}
q.add(child);
}
}
}失敗指標規則：若父節點為根，子節點 fail 指向根；否則沿父節點 fail 鏈尋找擁有相同字元轉移的節點，找不到則指向根。
// 任意匹配：是否存在至少一個模式
public boolean findAnyIn(CharSequence cs) {
Node node = root;
for (int i = 0, len = cs.length(); i < len; i++) {
Node next = node.childOf(cs.charAt(i));
if (next == null) {
next = node.fail();
if (next == null) { node = root; continue; }
}
if (next.exists()) return true;
node = next;
}
return false;
}
// 全量匹配：返回所有匹配位置與模式
public List<MatchInfo> search(CharSequence cs) {
if (cs == null || cs.length() == 0) return Collections.emptyList();
List<MatchInfo> res = new ArrayList<>();
Node node = root;
for (int i = 0, len = cs.length(); i < len; i++) {
Node next = node.childOf(cs.charAt(i));
if (next == null) {
next = node.fail();
if (next == null) { node = root; continue; }
}
if (next.exists()) {
res.add(new MatchInfo(i, next));
node = root; // 重置為根繼續匹配（可依需求調整為 node = next 以支援重疊匹配）
continue;
}
node = next;
}
return res;
}MatchInfopublic final class MatchInfo {
private final int index; // 0-based 起始位置
private final String word;
public MatchInfo(int endIndex, Node node) {
StringBuilder sb = new StringBuilder();
while (node != null && !node.isRoot()) {
sb.append(node.value());
node = node.parent();
}
String w = sb.reverse().toString();
this.word = w;
this.index = endIndex + 1 - w.length();
}
// getter、toString()...
}public static void main(String[] args) {
List<String> dict = Arrays.asList("say", "her", "he", "she", "shr", "alone");
WordTable table = WordTable.compile(dict);
System.out.println("Trie 結構：\n" + table);
String text = "1shesaynothingabouthislivinghimalone";
List<MatchInfo> matches = table.search(text);
System.out.println("匹配結果：" + matches);
}Trie 結構：
< exists="false" parent="null" fail="null">
<s exists="false" parent=" " fail=" ">
<a exists="false" parent="s" fail="a">
<y exists="true" parent="a" fail=" "></y>
</a>
<h exists="false" parent="s" fail="h">
<e exists="true" parent="h" fail="e"></e>
<r exists="true" parent="h" fail=" "></r>
</h>
</s>
<h exists="false" parent=" " fail=" ">
<e exists="true" parent="h" fail=" ">
<r exists="true" parent="e" fail=" "></r>
</e>
</h>
<a exists="false" parent=" " fail=" "> ... </a>
</ >
匹配結果：[1:she, 4:say, 31:alone]說明：在文本 1shesaynothingabouthislivinghimalone 中，位置 1 匹配 "she"，位置 4 匹配 "say"，位置 31 匹配 "alone"（索引為 0-based 起始位置）。
double-array trie 或 DAT 壓縮存儲。node = next 並沿 fail 鏈收集所有 exists() 節點。WordTable 建構後為不可變，可安全共享於多執行緒環境。本文提供了一個清晰、可直接用於生產的 AC 自動機 Java 實作，涵蓋 Trie 建構、失敗指標 BFS 建立、雙節點策略適配 ASCII/Unicode、匹配查詢與結果封裝。理解其核心邏輯（Trie + BFS Fail 指標），即可靈活應用於敏感詞過濾、日誌審計、基因序列比對等高效多模式匹配場景。
