AC自动机

在家"疯"控第四天,无聊,写博客消遣一下.

今天我们来讲AC自动机.

引入

我知道，很多人在第一次看到这个东西的时侯是非常兴奋的。（别问我为什么知道）不过这个自动机啊它叫作 Automaton，不是 Automation，让萌新失望啦。切入正题。似乎在初学自动机相关的内容时，许多人难以建立对自动机的初步印象，尤其是在自学的时侯。而这篇文章就是为你们打造的。笔者在自学 AC 自动机后花费两天时间制作若干的 gif，呈现出一个相对直观的自动机形态。尽管这个图似乎不太可读，但这绝对是在作者自学的时侯，画得最认真的 gif 了。另外有些小伙伴问这个 gif 拿什么画的。笔者用 Windows 画图软件制作(不知道今天是否还像昨天那样传不上去详见红黑树(4万字文章超详细,只为一个目的)_cyy_yyds(蒟蒻练习生)的博客-CSDN博客)。

概述

AC 自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的。

解释

简单来说，建立一个 AC 自动机有两个步骤：

基础的 Trie 结构：将所有的模式串构成一棵 Trie。
KMP 的思想：对 Trie 树上所有的结点构造失配指针。

然后就可以利用它进行多模式匹配了。

字典树构建

AC 自动机在初始时会将若干个模式串丢到一个 Trie 里，然后在 Trie 上建立 AC 自动机。这个 Trie 就是普通的 Trie，该怎么建怎么建。

这里需要仔细解释一下 Trie 的结点的含义，尽管这很小儿科，但在之后的理解中极其重要。Trie 中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态，Trie 的边就是状态的转移。

形式化地说，对于若干个模式串 $s_{1},s_{2}...s_{n}$ ，将它们构建一棵字典树后的所有状态的集合记作 $Q$ 。

失配指针

AC 自动机利用一个 fail 指针来辅助多模式串的匹配。

状态 $u$ 的 fail 指针指向另一个状态 $v$ ，其中 $v\epsilon q$ ，且 v是 u的最长后缀（即在若干个后缀状态中取最长的一个作为 fail 指针）。对于学过 KMP 的朋友，我在这里简单对比一下这里的 fail 指针与 KMP 中的 next 指针：

共同点：两者同样是在失配的时候用于跳转的指针。
不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

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

没看懂上面的对比不要急（也许我的脑回路和泥萌不一样是吧），你只需要知道，AC 自动机的失配指针指向当前状态的最长后缀状态即可。

AC 自动机在做匹配时，同一位上可匹配多个模式串。

构建指针

下面介绍构建 fail 指针的 基础思想：（强调！基础思想！基础！）

构建 fail 指针，可以参考 KMP 中构造 Next 指针的思想。

考虑字典树中当前的结点，u 的父结点是 p，通过字符 c 的边指向，即 $trie[p,c]=u$ 。假设深度小于 u的所有结点的 fail 指针都已求得。

如果 $trie[fail[p],c]$ 存在：则让 u 的 fail 指针指向 $trie[fail[p],c]$ 。相当于在 $p$ 和 $fail[p]$ 后面加一个字符 c，分别对应 $u$ 和 $fail[u]$ 。
如果 $trie[fail[p],c]$ 不存在：那么我们继续找到 $trie[fail[fail[p]],c]$ 。重复 1 的判断过程，一直跳 fail 指针直到根结点。
如果真的没有，就让 fail 指针指向根结点。

如此即完成了 $fail[u]$ 的构建。

例子

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

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

我们重点分析结点 6 的 fail 指针构建：

找到 6 的父结点 5，fail[5]=10。然而 10 结点没有字母 s 连出的边；继续跳到 10 的 fail 指针，fail[10]=0。发现 0 结点有字母 s 连出的边，指向 7 结点；所以 fail[6]=7。

字典树与字典图

我们直接上代码吧。字典树插入的代码就不分析了（后面完整代码里有），先来看构建函数 build()，该函数的目标有两个，一个是构建 fail 指针，一个是构建自动机。参数如下：

tr[u,c]：有两种理解方式。我们可以简单理解为字典树上的一条边，即 trie[u,c]；也可以理解为从状态（结点）u 后加一个字符 c 到达的状态（结点），即一个状态转移函数trans(u,c) 。下文中我们将用第二种理解方式继续讲解。
队列 q：用于 BFS 遍历字典树。
fail[u]：结点的 fail 指针。

void build() {
  for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]);
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u][i])
        fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
      else
        tr[u][i] = tr[fail[u]][i];
    }
  }
}

多模式匹配

接下来分析匹配函数 query()：

实现

int query(char *t) {
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u][t[i] - 'a'];  // 转移
    for (int j = u; j && e[j] != -1; j = fail[j]) {
      res += e[j], e[j] = -1;
    }
  }
  return res;
}

解释

这里 u作为字典树上当前匹配到的结点，res 即返回的答案。循环遍历匹配串，u 在字典树上跟踪当前字符。利用 fail 指针找出所有匹配的模式串，累加到答案中。然后清零。在上文中我们分析过，字典树的结构其实就是一个 trans 函数，而构建好这个函数后，在匹配字符串的过程中，我们会舍弃部分前缀达到最低限度的匹配。fail 指针则指向了更多的匹配状态。最后上一份图。对于刚才的自动机：

我们从根结点开始尝试匹配 ushersheishis，那么 p的变化将是：

红色结点： p结点
粉色箭头： p在自动机上的跳转，
蓝色的边：成功匹配的模式串
蓝色结点：示跳 fail 指针时的结点（状态）。

模板 1

LuoguP3808【模板】AC 自动机（简单版）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 6;
int n;

namespace AC {
int tr[N][26], tot;
int e[N], fail[N];

void insert(char *s) {
  int u = 0;
  for (int i = 1; s[i]; i++) {
    if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot;  // 如果没有则插入新节点
    u = tr[u][s[i] - 'a'];                              // 搜索下一个节点
  }
  e[u]++;  // 尾为节点 u 的串的个数
}

queue<int> q;

void build() {
  for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]);
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u][i]) {
        fail[tr[u][i]] =
            tr[fail[u]][i];  // fail数组：同一字符可以匹配的其他位置
        q.push(tr[u][i]);
      } else
        tr[u][i] = tr[fail[u]][i];
    }
  }
}

int query(char *t) {
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u][t[i] - 'a'];  // 转移
    for (int j = u; j && e[j] != -1; j = fail[j]) {
      res += e[j], e[j] = -1;
    }
  }
  return res;
}
}  // namespace AC

char s[N];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%s", s + 1), AC::insert(s);
  scanf("%s", s + 1);
  AC::build();
  printf("%d", AC::query(s));
  return 0;
}

模板 2

P3796【模板】AC 自动机（加强版）

#include <bits/stdc++.h>
using namespace std;
const int N = 156, L = 1e6 + 6;

namespace AC {
const int SZ = N * 80;
int tot, tr[SZ][26];
int fail[SZ], idx[SZ], val[SZ];
int cnt[N];  // 记录第 i 个字符串的出现次数

void init() {
  memset(fail, 0, sizeof(fail));
  memset(tr, 0, sizeof(tr));
  memset(val, 0, sizeof(val));
  memset(cnt, 0, sizeof(cnt));
  memset(idx, 0, sizeof(idx));
  tot = 0;
}

void insert(char *s, int id) {  // id 表示原始字符串的编号
  int u = 0;
  for (int i = 1; s[i]; i++) {
    if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot;
    u = tr[u][s[i] - 'a'];  // 转移
  }
  idx[u] = id;  // 以 u 为结尾的字符串编号为 idx[u]
}

queue<int> q;

void build() {
  for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]);
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u][i]) {
        fail[tr[u][i]] =
            tr[fail[u]][i];  // fail数组：同一字符可以匹配的其他位置
        q.push(tr[u][i]);
      } else
        tr[u][i] = tr[fail[u]][i];
    }
  }
}

int query(char *t) {  // 返回最大的出现次数
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u][t[i] - 'a'];
    for (int j = u; j; j = fail[j]) val[j]++;
  }
  for (int i = 0; i <= tot; i++)
    if (idx[i]) res = max(res, val[i]), cnt[idx[i]] = val[i];
  return res;
}
}  // namespace AC

int n;
char s[N][100], t[L];

int main() {
  while (~scanf("%d", &n)) {
    if (n == 0) break;
    AC::init();  // 数组清零
    for (int i = 1; i <= n; i++)
      scanf("%s", s[i] + 1), AC::insert(s[i], i);  // 需要记录该字符串的序号
    AC::build();
    scanf("%s", t + 1);
    int x = AC::query(t);
    printf("%d\n", x);
    for (int i = 1; i <= n; i++)
      if (AC::cnt[i] == x) printf("%s\n", s[i] + 1);
  }
  return 0;
}

哎,没想到今天图片又传不上来了!