AC Automaton

发表于

AC自动机是一个建立在字典树上的算法，可以在线性时间复杂度内完成多字符串匹配。

我们对于所有匹配字串建一颗字典树，接下来，参考 KMP 算法，我们建立一个 fail 指针，相当于 KMP 的 next 数组，表示我们在失配时跳转到的结点。

参考 next 数组的求法，我们可以在对字典树进行广度优先搜索的同时求出 fail 指针。

即对于结点 $v$ 的 fail 指针，一直从其 father 的 fail 指针向前跳，直到匹配为止。

需要注意的是如果一个字符串被匹配了，那么其 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
78
79
80
81
82
#include <cstdio>
#include <cstring>
#include <queue>

struct AC_Automaton {
    struct Node {
        struct Node *son[26], *fail, *father;
        int cnt;
        bool vis;

        Node(Node *father) : fail(0), father(father), cnt(0), vis(0) {
            memset(son, 0, sizeof(son));
        }
    } *trie;

    AC_Automaton() {
        trie = new Node(0);
    }

    inline void AddString(char *str) {
        Node *t = trie;
        while(*str) {
            if(!t->son[*str - 'a']) t->son[*str - 'a'] = new Node(t);
            t = t->son[*str - 'a'], str++;
        }
        t->cnt++;
    }

    inline void SetFail() {
        std::queue<Node *> que;
        que.push(trie);

        while(!que.empty()) {
            Node *x = que.front();
            que.pop();
            for(int i = 0; i < 26; i++) {
                if(x->son[i]) {
                    Node *&t = x->son[i]->fail;
                    t = x->fail;
                    while(t && !t->son[i]) t = t->fail;
                    if(t) t = t->son[i];
                    else t = trie;
                    
                    que.push(x->son[i]);
                }
            }
        }

        trie->fail = trie;
    }

    int FindIn(char *str)  {
        int ans = 0;
        if(!trie->fail) SetFail();
        Node *t = trie;
        while(*str) {
            if(t->son[*str - 'a']) {
                t = t->son[*str - 'a'];
                for(Node *x = t; x != trie && !x->vis; x = x->fail)
                    x->vis = 1, ans += x->cnt;
                str++;
            } else if(t == trie) str++;
            else t = t->fail;
        }
        return ans;
    }
};

char str[1000001];
AC_Automaton ac;

int main(int argc, char *argv[]) {
    int n;
    scanf("%d", &n);
    while(n--) {
        scanf("%s", str);
        ac.AddString(str);
    }
    scanf("%s", str);
    printf("%d", ac.FindIn(str));
    return 0;
}

有个 break 调了一晚上，头疼。。。

luogu3808 的代码，板子题。