java编程之AC自动机工作原理的示例分析
AC自动机是一种多模式匹配算法，常用于字符串匹配、关键词过滤、敏感词识别等应用场景。本文将从工作原理和示例两方面介绍AC自动机的实现方式。
一、工作原理
AC自动机的基本思路是将多个模式串构建成一棵树，并通过分支节点的失配指针（也叫跳转指针）进行匹配。具体的实现方式是对树进行广度遍历，对每个节点记录其前缀的最长匹配后缀，然后在搜索过程中利用失配指针将查询串进行跳转。
以模式串集合["he", "she", "his", "hers"]为例，构建出的AC自动机如下图所示：
从根节点开始遍历，分别记录以下节点的失配指针：
- 节点 h 的失配指针指向根节点，因为 h 无法匹配到根节点上的任何字符；
- 节点 he 的失配指针指向节点 h，因为he的前缀h无法匹配到节点he的后缀e；
- 节点 sh 的失配指针指向根节点，因为sh无法匹配到根节点的任何字符；
- 节点 his 的失配指针指向节点 h，因为his的前缀h无法匹配到节点his的后缀is；
- 节点 hers 的失配指针指向节点 sh，因为hers的前缀sh无法匹配到节点hers的后缀ers。
在查询串 "ushers" 的匹配过程中，从根节点开始进行遍历和匹配：
- 遇到 u，根据失配指针跳转到根节点。
- 遇到 s，根据失配指针跳转到节点 sh。
- 遇到 h，根据失配指针跳转到节点 h。
- 遇到 e，根据失配指针跳转到节点 he，匹配成功。
- 遇到 r，根据失配指针跳转到节点 hers。
- 遇到 s，根据失配指针跳转到节点 sh。
- 匹配结束，返回匹配到的模式串列表。
二、示例分析
下面介绍一下AC自动机的实现方式。代码示例主要分为两个部分：AC自动机的构建和匹配过程的实现。
构建过程：
public class AC {
private ACNode root; // 根节点
// 插入一个模式串
public void insert(String word) {
ACNode cur = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (!cur.children.containsKey(ch)) {
cur.children.put(ch, new ACNode()); // 创建子节点
}
cur = cur.children.get(ch);
}
cur.isEnd = true; // 标记一个单词的结束
}
// 构造AC自动机
public void build() {
Queue<ACNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
ACNode cur = queue.poll();
for (Map.Entry<Character, ACNode> entry : cur.children.entrySet()) {
char ch = entry.getKey();
ACNode child = entry.getValue();
// 1. 设置失败指针
if (cur == root) {
child.fail = root;
} else {
ACNode p = cur.fail; // p是cur的失败指针
while (p != null && !p.children.containsKey(ch)) {
p = p.fail;
}
child.fail = p == null ? root : p.children.get(ch);
}
// 2. 继承 pattern
child.isEnd |= child.fail.isEnd;
// 3. 入队
queue.offer(child);
}
}
}
}
这里的ACNode结构体定义如下：
class ACNode {
boolean isEnd; // 标记一个单词的结束
Map<Character, ACNode> children; // 子节点指针
ACNode fail; // 失败指针
public ACNode() {
isEnd = false;
children = new HashMap<>();
fail = null;
}
}
匹配过程：
public class AC {
// ...
// 在AC自动机上匹配一个字符串
public List<String> match(String text) {
List<String> res = new ArrayList<>();
ACNode cur = root;
for (int i = 0; i < text.length(); i++) {
char ch = text.charAt(i);
while (cur != root && !cur.children.containsKey(ch)) {
cur = cur.fail; // 失配跳转
}
cur = cur.children.containsKey(ch) ? cur.children.get(ch) : root;
// 更新结果列表
for (ACNode p = cur; p != root; p = p.fail) {
if (p.isEnd) {
res.add(text.substring(i - p.depth() + 1, i + 1));
}
}
}
return res;
}
}
这里需要注意一下失配跳转的处理方式，每次匹配失败后，我们沿着当前节点的失败指针不断向上跳转，直到找到一个子节点也包含当前字符。如果没有这样的子节点，说明已经跳转到了根节点，然后将当前节点设置为根节点。
完整代码如下：
`java
import java.util.*;
class ACNode {
boolean isEnd; // 标记一个单词的结束
Map<Character, ACNode> children; // 子节点指针
ACNode fail; // 失败指针
public ACNode() {
isEnd = false;
children = new HashMap<>();
fail = null;
}
public int depth() {
int depth = 0;
for (ACNode p = this; p != null && p != p.fail; p = p.fail) {
depth++;
}
return depth;
}
}
public class AC {
private ACNode root; // 根节点
// 插入一个模式串
public void insert(String word) {
ACNode cur = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (!cur.children.containsKey(ch)) {
cur.children.put(ch, new ACNode()); // 创建子节点
}
cur = cur.children.get(ch);
}
cur.isEnd = true; // 标记一个单词的结束
}
// 构造AC自动机
public void build() {
Queue<ACNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
ACNode cur = queue.poll();
for (Map.Entry<Character, ACNode> entry : cur.children.entrySet()) {
char ch = entry.getKey();
ACNode child = entry.getValue();
// 1. 设置失败指针
if (cur == root) {
child.fail = root;
} else {
ACNode p = cur.fail; // p是cur的失败指针
while (p != null && !p.children.containsKey(ch)) {
p = p.fail;
}
child.fail = p == null ? root : p.children.get(ch);
}
// 2. 继承 pattern
child.isEnd |= child.fail.isEnd;
// 3. 入队
queue.offer(child);
}
}
}
// 在AC自动机上匹配一个字符串
public List<String> match(String text) {
List<String> res = new ArrayList<>();
ACNode cur = root;
for (int i = 0; i < text.length(); i++) {
char ch = text.charAt(i);
while (cur != root && !cur.children.containsKey(ch)) {
cur = cur.fail; // 失配跳转
}
cur = cur.children.containsKey(ch) ? cur.children.get(ch) : root;
// 更新结果列表
for (AC