自动AC机？不，是AC自动机
今天我们来介绍一点进阶的知识——AC自动机。
AC自动机是啥
AC自动机是什么呢？是不是用了这个算法，不管什么题目都会自动AC呢？（别做梦啦~）
AC自动机，是Aho-Corasick automaton的简称，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。AC自动机是对字典树算法的一种延伸，是字符串中运用非常广泛的一种算法，但是NOIP一般不会涉及，多在省选及以上的比赛中出现。
AC自动机长啥样
AC自动机比字典树多维护一个数组——fail数组。fail数组的作用是指向当前节点表示的字符串的后缀可以和模式串匹配上的最大长度的节点。是不是和KMP的next数组有点相似？
KMP的next数组是自己和自己的匹配，而AC自动机的fail数组是自己和模式串（当然也包括自己）的匹配。看一下下面这张图，应该会对fail数组有深刻的理解。
AC自动机（红边为fail边，黑边为字典树的边）
这张图中的红色线条就是对应节点fail数组所指向的节点，都指向了能和改字符串后缀匹配的最长前缀。
具体构造方法
观察上面的那张图，一个节点的fail指针（暂且这么叫）指向的节点，和它的父节点（若u节点通过一步转移能到达v节点，则称u为v的父节点）fail指针指向的位置是有关系的。
既然只和父节点的fail指针有关，那么我们采用队列的数据结构和处理每个节点的fail指针。<u style="text-decoration: none; border-bottom: 1px dashed grey;">设当前节点为x</u>。
-
初始化时，应建立一个虚拟节点，将这个节点的所有出边连向根节点，把根节点的fail指针指向虚拟节点。（注意：根节点代表空串）
-
遍历x的每一种边（注意：是“种”，不是“条”，即包括没有的边）。（这部分仔细捋一捋）
-
如果x没有这条边，如果x的fail节点有连这种边，那么x的这条边连向fail节点的这种边连向的点。
-
如果x有这种边，那么<u style="text-decoration: none; border-bottom: 1px dashed grey;">其连向的节点</u>的fail指向x的fail的这种边连向的点。
Code
struct node {
node* nxt[26];
node* fail;
int id;
node() {
fail = NULL; id = -1;
for (int i = 0; i < 26; ++i)
nxt[i] = NULL;
}
};
class AC_Machine {
public:
void init() {
root = new node[1];
emp = new node[1];
}
int get_id(node *x) { return x->id; }
node *get_root() { return root; }
node *get_nxt(node *x, int k) { return x->nxt[k]; }
node *get_fail(node *x) { return x->fail; }
void insert(char *c, int id) {
int len = strlen(c);
node *now = root;
for (int i = 0; i < len; ++i) {
int x = c[i] - 'a';
if ((now->nxt[x]) == NULL)
now->nxt[x] = new node[1];
now = now->nxt[x];
}
now->id = id;
}
void build() {
node *now;
queue <node *> q;
root->fail = emp;
for (int i = 0; i < 26; ++i)
emp->nxt[i] = root;
q.push(root);
while (!q.empty()) {
now = q.front(); q.pop();
for (int i = 0; i < 26; ++i) {
if ((now->nxt[i]) == NULL) {
now->nxt[i] = now->fail->nxt[i];
} else {
now->nxt[i]->fail = now->fail->nxt[i];
q.push(now->nxt[i]);
}
}
}
}
private:
node *root, *emp;
void clean(node *ro) {
for (int i = 0; i < 26; ++i)
if (ro->nxt[i] != NULL)
clean(ro->nxt[i]);
delete ro;
}
}t;
【信息学竞赛从入门到巅峰】，一个专注于分享OI/ACM常用算法及知识的公众号。
关于AC自动机的经典应用，可以在公众号中回复【AC自动机】获取哦。
