0%

AC自动机

发表于 更新于 分类于 ，

本来想先讲讲自动机的概念，不过又觉得没有什么必要。理解AC自动机并不需要太多关于自动机的知识。

情景引入与分析

给出一个字典包含若干个单词，再给出一个长字符串。问在这个长字符串S中出现了多少次字典中的单词。

假设字典内有N个串，平均长度为L，长字符串长度为M。

朴素的想法，对每个单词在长字符串中查找出现了几次，时间复杂度为 O(N*(M+l)) 这还是建立在匹配用了kmp的情况下。

又考虑用字典跑出一个字典树，用S的每一位做开始进行匹配。时间复杂度 M*max(l).

其中一个可优化时间的地方就是，当匹配失效后。不应该在从S的下一位重新跑字典树，这浪费了已经匹配了若干位的已经信息。
所以考虑对已经匹配的串，找到它的最长的在字典树中存在的后缀。这里有点绕口，拆分下条件.
寻找一个串:

  1. 是已经匹配的串的后缀
  2. 这个串用在字典树上可以表示
  3. 尽可能长

这个过程与KMP非常相似，回想KMP匹配失效后寻找的是 已经匹配串的最长公共前缀后缀串，然后从这个位置开始重新匹配。
对于字典树上匹配失败，那么应当在字典的所有串中找一个 最长的前缀使得同时为已经匹配串的后缀。本质上时间上是相同的东西，不过字典中是多个串，所以是从多个串中找。

又字典树上的每个结点都代表一个串的前缀，故匹配失效后，是想找到一个节点，从那个结点继续匹配。在kmp的过程中，我们预处理出了next数组，来找到了每一个寻找关系。 在这里我们需要做的事是一样的，为每一个匹配失效的结点找一个结点。对于某节点A通过这种关系找到了B结点，我们称为A的fail指针指向B。fail指针中文名为失配指针

基本过程

建字典树

这部分和普通的字典树没有区别。
不过Node的数据多了一个表示fail指针

构建fail指针

fail的构建方法是这样的：

对于一个节点C，标识字符a，记C的父亲节点为T，T的fail指针指向S结点。
若S的子结点中存在结点P标识字符也为a，则C->fail=P;
否则 继续沿S的失配指针走，即S=S->fail

如果找不到这个节点，那么C->fail=root

在实际操作时，是用广搜来实现，因为这个建构过程要求父亲节点的失配指针已经建好，而且一层层都要建好.
另外，root的子节点一定指向root

查询

查询的部分一般要根据题意来进行修改。
不过一般的方法都是对长字符串S进行匹配，若是失配则沿当前已经匹配结点的fail指针不停跳转到新的结点，直到找到新节点的子结点可以匹配/或者一直跳到root，然后视为匹配成功。

每次匹配的成功一次后。计算当前匹配结点fail链上所有结点，依次记录值。注意不要重复访问结点。

模板代码

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
struct Trie {
    static const char stdc = 'a';
    int ch[N][26];
    int val[N];
    int num[N];
    int root;
    int fail[N];
    int sz;
    int idx(char c) {
        return c - stdc;
    }
    void init() {
        root = 0;
        sz = 1;
        memset(val, 0, sizeof val);
        memset(num, 0, sizeof num);
        memset(ch[0], 0, sizeof ch[0]);
    }

    void insert(char *str) {
        int len = strlen(str);
        int s = 0;
        for (int i = 0; i < len; ++i) {
            int u = idx(str[i]);
            if (!ch[s][u]) {
                memset(ch[sz], 0, sizeof ch[sz]);
                ch[s][u] = sz++;
            }
            s = ch[s][u]息
            num[s]++;
        }
        val[s]++;
    }
    void build() {
        queue<int> Q;
        fail[0] = 0;
        for (int i = 0; i < 26; ++i) {
            int u = ch[0][i];
            if (u) {
                fail[u] = 0;
                Q.push(u);
            }
        }
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int i = 0; i < 26; ++i) {
                int r = ch[u][i];
                if (!r) {
                    continue;
                }
                Q.push(r);
                int v = fail[u];
                while (v && !ch[v][i]) v = fail[v];
                fail[r] = ch[v][i];
            }
        }
    }
    int query(char *str) {
        int s = root, ans = 0;
        int len = strlen(str);
        for (int i = 0; i < len; ++i) {
            int id = idx(str[i]);
            while (s && !ch[s][id]) {
                s = fail[s];
            }
            s = ch[s][id];
            int u = s;
            while (u && val[u] != -1) {
                ans += val[u];
                val[u] = -1;
                u = fail[u];
            }
        }
        return ans;
    }
} ac;

时间复杂度分析

假设字典内有N个串，平均长度为L，长字符串长度为M。
建立Trie树：O(N*L)
建立fail指针：O(N*L)
模式匹配：O(M)
所以，总时间复杂度为:O(NL+M)。