前言

一个神清气爽，两个永不疲劳，三个长生不老！

AC 自动机，倍儿好！

前置知识

• \(Trie\)

• \(KMP\)

本文不作过多阐释。

视频讲解

看了 b 站的一个讲解视频，个人觉得把原理讲的很清楚，可以看看。

[算法]轻松掌握ac自动机

以及本文的参考链接：

AC 自动机

定义

\(AC\) 自动机（ \(Automaton\) ）：在 \(Trie\) 树上的 \(KMP\)。

建立过程

• 先将给出的所有字符串建成一棵 \(Trie\) 树

• 在 \(Trie\) 树上运用 \(KMP\) 的思想对所有结点构造失配指针（ \(fail[]\) ）

完成以上两个操作之后，就可以在 自动机 进行 多模式匹配 了。

失配指针（fail）

定义

定义： 用来辅助 \(AC\) 自动机进行多模式匹配的指针数组。

即，假定在 \(Trie\) 树上遍历至 \(x\) 得到的字符串为 \(word_x\)，且 \(fail[x]\) 指向的是 \(y\)。（废话文学）

那么，\(word_y\) 就是 \(word_x\) 在这棵 \(Trie\) 树上所能匹配到的最长后缀。

可以跟 \(KMP\) 的 \(next\) 指针进行类比，两者都是失配时用于跳转的指针，而不同点则是：

\(next\) 指针求的是最长的相同前后），而 \(fail\) 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

因为 KMP 只对一个模式串做匹配，而 AC 自动机要对多个模式串做匹配。有可能 fail 指针指向的结点对应着另一个模式串，两者前缀不同。—— oi-wiki

不理解的可以听一听我挂的 b 站链接，跟着 up 主推一遍，应该就可以轻松理解了。

构建指针

• 先将 \(Trie\) 树中所有字符串的首字母添加进队列中。

queue<int> q;
  for(int i = 0; i < 26; i ++) {
    if(tr[0][i]) q.push(tr[0][i]);
  }

• 遍历 \(Trie\) 树中 所有存在的结点， 每次枚举 当前结点 的 所有子结点。

int now;
while(!q.empty()) {
  now = q.front(), q.pop();
  for(int i = 0; i < 26; i ++) {
    if(tr[now][i]) {
      fail[tr[now][i]] = tr[fail[now]][i];
      q.push(tr[now][i]);
    }
    else tr[now][i] = tr[fail[now]][i];
  }
}

• 如果枚举的子结点存在，就可以通过 父亲结点 的 失配结点 \(fail\) 更新 该子结点 的 失配结点，同时将 该子结点 丢进队列里。

if(tr[now][i]) {
  fail[tr[now][i]] = tr[fail[now]][i];
  q.push(tr[now][i]);
}

• 否则，子结点不存在，直接更新节点编号信息即可。

else tr[now][i] = tr[fail[now]][i];

可以通过 \(oi-wiki\) 中的例子理解一下。

下面放一张 \(GIF\) 帮助大家理解。对字符串 \(i\)、 \(he\)、 \(his\)、 \(she\)、 \(hers\) 组成的字典树构建 \(fail\) 指针：

• 黄色结点：当前的结点 。
• 绿色结点：表示已经 \(BFS\) 遍历完毕的结点。
• 橙色的边：\(fail\) 指针。
• 红色的边：当前求出的 \(fail\) 指针。

构造全过程

由于本人太懒， 所以 \(trie\) 树的构建过程不讲。

下面直接给出构造代码，感觉只要 \(fail\) 指针的构造理解了，其他的都很简单。

void ins() {
	int len = strlen(s), v, now = 0;
	for(int i = 0; i < len; i ++) {
		v = s[i] - 'a';
		if(!tr[now][v]) tr[now][v] = ++cnt;
		now = tr[now][v];
	}
	num[now] = len;
}

void getfail() {
	queue<int> q;
	for(int i = 0; i < 26; i ++) {
		if(tr[0][i]) q.push(tr[0][i]);
	}
	int now;
	while(!q.empty()) {
		now = q.front(), q.pop();
		for(int i = 0; i < 26; i ++) {
			if(tr[now][i]) {
				fail[tr[now][i]] = tr[fail[now]][i];
				q.push(tr[now][i]);
			}
			else tr[now][i] = tr[fail[now]][i];
		}
	}
}

原文地址：http://www.cnblogs.com/Spring-Araki/p/16794628.html