跳转至

AC 自动机

AC 自动机是 以 Trie 的结构为基础,结合 KMP 的思想 建立的自动机,用于解决多模式匹配等任务。

引入

我知道,很多人在第一次看到这个东西的时侯是非常兴奋的。(别问我为什么知道)不过这个自动机啊它叫作 Automaton,不是 Automation,让萌新失望啦。切入正题。似乎在初学自动机相关的内容时,许多人难以建立对自动机的初步印象,尤其是在自学的时侯。而这篇文章就是为你们打造的。笔者在自学 AC 自动机后花费两天时间制作若干的 gif,呈现出一个相对直观的自动机形态。尽管这个图似乎不太可读,但这绝对是在作者自学的时侯,画得最认真的 gif 了。另外有些小伙伴问这个 gif 拿什么画的。笔者用 Windows 画图软件制作。

解释

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

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

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

字典树构建

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

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

形式化地说,对于若干个模式串 \(s_1,s_2\dots s_n\),将它们构建一棵字典树后的所有状态的集合记作 \(Q\)

失配指针

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

状态 \(u\) 的 fail 指针指向另一个状态 \(v\),其中 \(v\in Q\),且 \(v\)\(u\) 的最长后缀(即在若干个后缀状态中取最长的一个作为 fail 指针)。对于学过 KMP 的朋友,我在这里简单对比一下这里的 fail 指针与 KMP 中的 next 指针:

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

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

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

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

构建指针

下面介绍构建 fail 指针的 基础思想:(强调!基础思想!基础!)

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

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

  1. 如果 \(\text{trie}[\text{fail}[p],\mathtt{c}]\) 存在:则让 u 的 fail 指针指向 \(\text{trie}[\text{fail}[p],\mathtt{c}]\)。相当于在 \(p\)\(\text{fail}[p]\) 后面加一个字符 c,分别对应 \(u\)\(fail[u]\)
  2. 如果 \(\text{trie}[\text{fail}[p],\mathtt{c}]\) 不存在:那么我们继续找到 \(\text{trie}[\text{fail}[\text{fail}[p]],\mathtt{c}]\)。重复 1 的判断过程,一直跳 fail 指针直到根结点。
  3. 如果真的没有,就让 fail 指针指向根结点。

如此即完成了 \(\text{fail}[u]\) 的构建。

例子

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

  1. 黄色结点:当前的结点 \(u\)
  2. 绿色结点:表示已经 BFS 遍历完毕的结点,
  3. 橙色的边:fail 指针。
  4. 红色的边:当前求出的 fail 指针。

AC_automation_gif_b_3.gif

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

AC_automation_6_9.png

找到 6 的父结点 5,\(\text{fail}[5]=10\)。然而 10 结点没有字母 s 连出的边;继续跳到 10 的 fail 指针,\(\text{fail}[10]=0\)。发现 0 结点有字母 s 连出的边,指向 7 结点;所以 \(\text{fail}[6]=7\)。最后放一张建出来的图

finish

字典树与字典图

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

  1. tr[u,c]:有两种理解方式。我们可以简单理解为字典树上的一条边,即 \(\text{trie}[u,c]\);也可以理解为从状态(结点)\(u\) 后加一个字符 c 到达的状态(结点),即一个状态转移函数 \(\text{trans}(u,c)\)。下文中我们将用第二种理解方式继续讲解。
  2. 队列 q:用于 BFS 遍历字典树。
  3. fail[u]:结点 \(u\) 的 fail 指针。
实现
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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];
    }
  }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def build():
    for i in range(0, 26):
        if tr[0][i] == 1:
            q.append(tr[0][i])
    while len(q) > 0:
        u = q[0]
        q.pop()
        for i in range(0, 26):
            if tr[u][i] == 1:
                fail[tr[u][i]] = tr[fail[u]][i]
                q.append(tr[u][i])
            else:
                tr[u][i] = tr[fail[u]][i]

解释

解释一下上面的代码:build 函数将结点按 BFS 顺序入队,依次求 fail 指针。这里的字典树根结点为 0,我们将根结点的子结点一一入队。若将根结点入队,则在第一次 BFS 的时候,会将根结点儿子的 fail 指针标记为本身。因此我们将根结点的儿子一一入队,而不是将根结点入队。

然后开始 BFS:每次取出队首的结点 u(\(\text{fail}[u]\) 在之前的 BFS 过程中已求得),然后遍历字符集(这里是 0-25,对应 a-z,即 \(u\) 的各个子节点):

  1. 如果 \(\text{trans}[u][\mathtt{i}]\) 存在,我们就将 \(\text{trans}[u][\mathtt{i}]\) 的 fail 指针赋值为 \(\text{trans}[\text{fail}[u]][\mathtt{i}]\)。这里似乎有一个问题。根据之前的讲解,我们应该用 while 循环,不停的跳 fail 指针,判断是否存在字符 i 对应的结点,然后赋值,但是这里通过特殊处理简化了这些代码。
  2. 否则,令 \(\text{trans}[u][\mathtt{i}]\) 指向 \(\text{trans}[\text{fail}[u]][\mathtt{i}]\) 的状态。

这里的处理是,通过 else 语句的代码修改字典树的结构。没错,它将不存在的字典树的状态链接到了失配指针的对应状态。在原字典树中,每一个结点代表一个字符串 \(S\),是某个模式串的前缀。而在修改字典树结构后,尽管增加了许多转移关系,但结点(状态)所代表的字符串是不变的。

\(\text{trans}[S][\mathtt{c}]\) 相当于是在 \(S\) 后添加一个字符 c 变成另一个状态 \(S'\)。如果 \(S'\) 存在,说明存在一个模式串的前缀是 \(S'\),否则我们让 \(\text{trans}[S][\mathtt{c}]\) 指向 \(\text{trans}[\text{fail}[S]][\mathtt{c}]\)。由于 \(\text{fail}[S]\) 对应的字符串是 \(S\) 的后缀,因此 \(\text{trans}[\text{fail}[S]][\mathtt{c}]\) 对应的字符串也是 \(S'\) 的后缀。

换言之在 Trie 上跳转的时侯,我们只会从 \(S\) 跳转到 \(S'\),相当于匹配了一个 \(S'\);但在 AC 自动机上跳转的时侯,我们会从 \(S\) 跳转到 \(S'\) 的后缀,也就是说我们匹配一个字符 c,然后舍弃 \(S\) 的部分前缀。舍弃前缀显然是能匹配的。那么 fail 指针呢?它也是在舍弃前缀啊!试想一下,如果文本串能匹配 \(S\),显然它也能匹配 \(S\) 的后缀。所谓的 fail 指针其实就是 \(S\) 的一个后缀集合。

tr 数组还有另一种比较简单的理解方式:如果在位置 \(u\) 失配,我们会跳转到 \(\text{fail}[u]\) 的位置。所以我们可能沿着 fail 数组跳转多次才能来到下一个能匹配的位置。所以我们可以用 tr 数组直接记录记录下一个能匹配的位置,这样就能节省下很多时间。

这样修改字典树的结构,使得匹配转移更加完善。同时它将 fail 指针跳转的路径做了压缩(就像并查集的路径压缩),使得本来需要跳很多次 fail 指针变成跳一次。

过程

好的,我知道大家都受不了长篇叙述。上图!我们将之前的 GIF 图改一下:

AC_automation_gif_b_pro3.gif

  1. 蓝色结点:BFS 遍历到的结点 u
  2. 蓝色的边:当前结点下,AC 自动机修改字典树结构连出的边。
  3. 黑色的边:AC 自动机修改字典树结构连出的边。
  4. 红色的边:当前结点求出的 fail 指针
  5. 黄色的边:fail 指针
  6. 灰色的边:字典树的边

可以发现,众多交错的黑色边将字典树变成了 字典图。图中省略了连向根结点的黑边(否则会更乱)。我们重点分析一下结点 5 遍历时的情况。我们求 \(\text{trans}[5][s]=6\) 的 fail 指针:

AC_automation_b_7.png

本来的策略是找 fail 指针,于是我们跳到 \(\text{fail}[5]=10\) 发现没有 s 连出的字典树的边,于是跳到 \(\text{fail}[10]=0\),发现有 \(\text{trie}[0][s]=7\),于是 \(\text{fail}[6]=7\);但是有了黑边、蓝边,我们跳到 \(\text{fail}[5]=10\) 之后直接走 \(\text{trans}[10][s]=7\) 就走到 \(7\) 号结点了。

这就是 build 完成的两件事:构建 fail 指针和建立字典图。这个字典图也会在查询的时候起到关键作用。

多模式匹配

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

实现

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def query(t):
    u, res = 0, 0
    i = 1
    while t[i] == False:
        u = tr[u][t[i] - ord('a')]
        j = u
        while j == True and e[j] != -1:
            res += e[j]
            e[j] = -1
            j = fail[j]
        i += 1
    return res

解释

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

AC_automation_b_13.png

我们从根结点开始尝试匹配 ushersheishis,那么 \(p\) 的变化将是:

AC_automation_gif_c.gif

  1. 红色结点:\(p\) 结点
  2. 粉色箭头:\(p\) 在自动机上的跳转,
  3. 蓝色的边:成功匹配的模式串
  4. 蓝色结点:示跳 fail 指针时的结点(状态)。

总结

希望大家看懂了文章。

时间复杂度:定义 \(|s_i|\) 是模板串的长度,\(|S|\) 是文本串的长度,\(|\Sigma|\) 是字符集的大小(常数,一般为 26)。如果连了 trie 图,时间复杂度就是 \(O(\sum|s_i|+n|\Sigma|+|S|)\),其中 \(n\) 是 AC 自动机中结点的数目,并且最大可以达到 \(O(\sum|s_i|)\)。如果不连 trie 图,并且在构建 fail 指针的时候避免遍历到空儿子,时间复杂度就是 \(O(\sum|s_i|+|S|)\)

模板 1

Luogu P3808【模板】AC 自动机(简单版)

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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

Luogu P3796【模板】AC 自动机(加强版)

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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;
}
模版 3

Luogu P5357【模板】AC 自动机(二次加强版)

C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <deque>
#include <iostream>

void promote() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  std::cout.tie(0);
  return;
}

typedef char chr;
typedef std::deque<int> dic;

const int maxN = 2e5;
const int maxS = 2e5;
const int maxT = 2e6;

int n;
chr s[maxS + 10];
chr t[maxT + 10];
int cnt[maxN + 10];

struct AhoCorasickAutomaton {
  struct Node {
    int son[30];
    int val;
    int fail;
    int head;
    dic index;
  } node[maxS + 10];

  struct Edge {
    int head;
    int next;
  } edge[maxS + 10];

  int root;
  int ncnt;
  int ecnt;

  void Insert(chr *str, int i) {
    int u = root;
    for (int i = 1; str[i]; i++) {
      if (node[u].son[str[i] - 'a' + 1] == 0)
        node[u].son[str[i] - 'a' + 1] = ++ncnt;
      u = node[u].son[str[i] - 'a' + 1];
    }
    node[u].index.push_back(i);
    return;
  }

  void Build() {
    dic q;
    for (int i = 1; i <= 26; i++)
      if (node[root].son[i]) q.push_back(node[root].son[i]);
    while (!q.empty()) {
      int u = q.front();
      q.pop_front();
      for (int i = 1; i <= 26; i++) {
        if (node[u].son[i]) {
          node[node[u].son[i]].fail = node[node[u].fail].son[i];
          q.push_back(node[u].son[i]);
        } else {
          node[u].son[i] = node[node[u].fail].son[i];
        }
      }
    }
    return;
  }

  void Query(chr *str) {
    int u = root;
    for (int i = 1; str[i]; i++) {
      u = node[u].son[str[i] - 'a' + 1];
      node[u].val++;
    }
    return;
  }

  void addEdge(int tail, int head) {
    ecnt++;
    edge[ecnt].head = head;
    edge[ecnt].next = node[tail].head;
    node[tail].head = ecnt;
    return;
  }

  void DFS(int u) {
    for (int e = node[u].head; e; e = edge[e].next) {
      int v = edge[e].head;
      DFS(v);
      node[u].val += node[v].val;
    }
    for (auto i : node[u].index) cnt[i] += node[u].val;
    return;
  }

  void FailTree() {
    for (int u = 1; u <= ncnt; u++) addEdge(node[u].fail, u);
    DFS(root);
    return;
  }
} ACM;

int main() {
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    std::cin >> (s + 1);
    ACM.Insert(s, i);
  }
  ACM.Build();
  std::cin >> (t + 1);
  ACM.Query(t);
  ACM.FailTree();
  for (int i = 1; i <= n; i++) std::cout << cnt[i] << '\n';
  return 0;
}

拓展

确定有限状态自动机

如果大家理解了上面的讲解,那么作为拓展延伸,文末我们简单介绍一下 自动机KMP 自动机。(现在你再去看自动机的定义就会好懂很多啦)

有限状态自动机(Deterministic Finite Automaton,DFA)是由

  1. 状态集合 \(Q\)
  2. 字符集 \(\Sigma\)
  3. 状态转移函数 \(\delta:Q\times \Sigma \to Q\),即 \(\delta(q,\sigma)=q',\ q,q'\in Q,\sigma\in \Sigma\)
  4. 一个开始状态 \(s\in Q\)
  5. 一个接收的状态集合 \(F\subseteq Q\)

组成的五元组 \((Q,\Sigma,\delta,s,F)\)

那这东西你用 AC 自动机理解,状态集合就是字典树(图)的结点;字符集就是 az(或者更多);状态转移函数就是 \(\text{trans}(u,c)\) 的函数(即 \(\text{trans}[u][c]\));开始状态就是字典树的根结点;接收状态就是你在字典树中标记的字符串结尾结点组成的集合。

KMP 自动机

KMP 自动机就是一个不断读入待匹配串,每次匹配时走到接受状态的 DFA。如果共有 \(m\) 个状态,第 \(i\) 个状态表示已经匹配了前 \(i\) 个字符。那么我们定义 \(\text{trans}_{i,c}\) 表示状态 \(i\) 读入字符 \(c\) 后到达的状态,\(\text{next}_{i}\) 表示 prefix function,则有:

\[ \text{trans}_{i,c} = \begin{cases} i + 1, & \text{if }b_{i} = c \\[2ex] \text{trans}_{\text{next}_{i},c}, & \text{otherwise} \end{cases} \]

(约定 \(\text{next}_{0}=0\)

我们发现 \(\text{trans}_{i}\) 只依赖于之前的值,所以可以跟 KMP 一起求出来。(一些细节:走到接受状态之后立即转移到该状态的 next)

时间和空间复杂度:\(O(m|\Sigma|)\)

对比之下,AC 自动机其实就是 Trie 上的自动机。(虽然一开始丢给你这句话可能不知所措)