Luobuyu's Blog

0%

AC自动机

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 5.2k 阅读时长 ≈ 5 分钟
AC自动机基本原理与用法。

AC自动机

一、定义

AC自动机用于多模式匹配，类似树上 kmp 算法。但是 kmp 只有一个模式串，AC 自动机有多个模式串，可以用多个模式串匹配要查询的字符串。

二、原理

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

  • 构造模式串的Trie树
  • 对Trie树上的所有节点构造失配指针fail（类似kmp中的next数组）

失配指针

多模式串匹配时，假设 $ pre1, pre2 $ ，如果原串在 $ pre1 $ 匹配失败，则会跳到最长的一个 $ pre1 $ 的后缀处继续匹配。fail指针指向失配串的最长后缀。

fail指针与next数组的异同点

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

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

构造失配指针

考虑字典树中当前的结点 $ u $ ， $ u $ 的父节点是 $ p $ ， $ p $ 通过字符 $ c $ 的边指向 $ u $ ，即 $ trie[p][c] = u $ 。假设深度小于 $ u $ 的所有节点的 fail 指针都已经求出来了。那么现在构造 $ u $ 的失配指针。

  • 如果 $ trie[fail[p]][c] $ 存在（也就是父节点的失配指针后面加一个字符 $ c $ ），那么让 $ u $ 的 fail 指针指向 $ trie[fail[p]][c] $ 。相当于在 $ p $ 和 $ fail[p] $ 后面加了一个字符 $ c $ ，分别对应 $ u $ 和 $ fail[u] $ 。
  • 如果 $ trie[fail[p]][c] $ 不存在，则继续向上找 $ trie[fail[fail[p]]][c] $ ，贪心的找最长后缀。一直跳到根节点。
  • 如果根节点也不存在，那么就让 $ fail[u] $ 指向根节点。

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

AC_automation_gif_b_3.gif

假设 $ u = 6 $ ，先找父节点 $ 5 $ ， $ 5 $ 的fail指针指向 $ 10 $

$ 10 $ 没有 $ s $ 边，继续找 $ 10 $ 的fail， $ 10 $ 的fail指向 $ 0 $

$ 0 $ 存在 $ s $ 边，所以 $ 6 $ 的fail指向 $ 7 $

finish

构造的代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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];
    }
  }
}

构建时使用 $ BFS $ 遍历，一次求队列内结点的 fail 指针。注意不将根节点入队，而是将根节点的子节点入队（如果将根节点 $ root $ 入队，会将根节点的儿子 $ u $ 的fail指针设置为 $ fail[u] = tr[root][c] = u $ ，设置成了自身。因此应该把根节点的孩子入队，同时把孩子的fail指针标记为 $ 0 $ ，可能已经被初始化过了，不用标记）。

然后每次取出队首节点 $ u $ ，遍历字符集：

  • 如果 $ tr[u][i] $ 存在，将 $ tr[u][i] $ 的 fail 指针赋值为 $ tr[fail[u]][i] $ 。（本来应该使用while循环，不停向前跳，但是这里通过路径压缩简化了代码，通过else语句代码修改字典树结构，将不存在的字典树的状态链接到了失配指针对应的状态，相当于转移了一个模式串。）这样就得到了自动机。类似编译原理中的自动机。
  • 如果 $ tr[u][i] $ 不存在，则令 $ tr[u][i] $ 指向 $ tr[fail[u]][i] $ ，路径压缩
    AC_automation_gif_b_pro3.gif

匹配查询

匹配查询的代码如下所示：

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;
}

每次在字典图上走一个节点，然后访问fail指针，找能够匹配的所有的模式串，加到答案上，然后清零，将该模式串标记为已经统计过了。

复杂度分析：

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

例题P3808 【模板】AC 自动机（简单版）

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
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
struct ACTrie
{
    const static int M = 26;
    const static int maxn = 1e6 + 10;
    int next[maxn][M] = {}, fail[maxn] = {}, cnt = 0;
    int exist[maxn] = {};
    queue<int> q;
    void insert(char *s)
    {
        int now = 0, len = strlen(s);
        for (int i = 0; i < len; ++i)
        {
            int c = s[i] - 'a';
            if (!next[now][c])
                next[now][c] = ++cnt;
            now = next[now][c];
        }
        exist[now]++;
    }

    void build()
    {

        for (int i = 0; i < M; ++i)
        {
            if (next[0][i])
            {
                fail[next[0][i]] = 0;
                q.push(next[0][i]);
            }
        }
        while (q.size())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < M; ++i)
            {
                if (next[u][i])
                {
                    fail[next[u][i]] = next[fail[u]][i];
                    q.push(next[u][i]);
                }
                else
                    next[u][i] = next[fail[u]][i];
            }
        }
    }

    int query(char *s)
    {
        int now = 0, len = strlen(s), ans = 0;
        for (int i = 0; i < len; ++i)
        {
            int c = s[i] - 'a';
            now = next[now][c];
            for (int j = now; j && exist[j] != 0; j = fail[j])
            {
                ans += exist[j];
                exist[j] = 0;
            }
        }
        return ans;
    }
};
char a[maxn];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    ACTrie trie;
    for (int i = 0; i < n; ++i)
    {
        cin >> a;
        trie.insert(a);
    }
    trie.build();
    cin >> a;
    cout << trie.query(a) << endl;
    return 0;
}

使用node版

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
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
struct Node
{
    const static int M = 26;
    int next[M];
    int exist;
    int fail;
} trie[maxn];
int cnt = 0;
void insert(char *s)
{
    int now = 0, len = strlen(s);
    for (int i = 0; i < len; ++i)
    {
        int c = s[i] - 'a';
        if (!trie[now].next[c])
            trie[now].next[c] = ++cnt;
        now = trie[now].next[c];
    }
    trie[now].exist++;
}
queue<int> q;
void build()
{
    for (int i = 0; i < 26; ++i)
    {
        int child = trie[0].next[i];
        if (child)
        {
            trie[child].fail = 0;
            q.push(child);
        }
    }
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; ++i)
        {
            int child = trie[u].next[i];
            if (child)
            {
                trie[child].fail = trie[trie[u].fail].next[i];
                q.push(child);
            }
            else
                trie[u].next[i] = trie[trie[u].fail].next[i];
        }
    }
}

int query(char *s)
{
    int u = 0, len = strlen(s), ans = 0;
    for (int i = 0; i < len; ++i)
    {
        u = trie[u].next[s[i] - 'a'];
        for (int j = u; j && trie[j].exist; j = trie[j].fail)
        {
            ans += trie[j].exist;
            trie[j].exist = 0;
        }
    }
    return ans;
}
char a[maxn];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a;
        insert(a);
    }
    build();
    cin >> a;
    cout << query(a) << endl;
    return 0;
}

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