Jiez19971225‘s Blog

做自己爱做的事

0%

AC自动机

发表于 更新于 分类于   |   字数统计: 1.8k(字)   |   阅读时长: 8(分)

因为看编译原理的有穷自动机，想到了以前一直不懂的这玩意。既然都叫自动机，就一块研究了吧。

AC 自动机是一种实现多模式匹配的字符串匹配算法。

前置技能 Trie 树（字典树）

字典树是一颗树，能迅速匹配字典中的字符串。
它具有以下基本性质。

  • 根节点不包括字符串，除根节点外每一个节点都只包含一个字符。
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  • 每个节点的所有子节点包含的字符都不相同

他的节点结构如下，其中 exist 标记当前节点是否是单词的结尾。

1
2
3
4
5
struct node
{
    node *next[26];
    bool exist;
}

以下是使用指针方式的构建代码,比较易懂

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
#include <bits/stdc++.h>
using namespace std;

struct trie
{
    struct node
    {
        node *next[26];
        bool exist;
        node()
        {
            memset(next, 0, sizeof(next));
            exist = false;
        }
    };
    node *root;
    trie()
    {
        root = new node();
    };
    void insert(string word)
    {
        node *cur = root;
        for (int i = 0; i < word.length(); ++i)
        {
            int num = word[i] - 'a';
            if (!cur->next[num])
            {
                cur->next[num] = new node();
                cur = cur->next[num];
            }
            else
            {
                cur = cur->next[num];
            }
        }
        cur->exist = true;
    }
    bool find(string word)
    {
        node *cur = root;
        bool ok = true;
        for (int i = 0; i < word.length(); ++i)
        {
            int num = word[i] - 'a';
            if (!cur->next[num])
            {
                ok = false;
                break;
            }
            cur = cur->next[num];
        }
        if (!cur->exist)
        {
            ok = false;
        }
        return ok;
    }
};

main()
{
    trie t;
    t.insert("hello");
    t.insert("world");
    t.insert("i");
    t.insert("am");
    t.insert("a");
    t.insert("lvjie");
    cout << t.find("lvjie") << endl;
    cout << t.find("lvji") << endl;
    cout << t.find("i") << endl;
    cout << t.find("a") << endl;
}

字典树

利用字典树暴力求解多模式匹配

很容易想到，从字符串的每一个字符开始，跑 Trie 的匹配算法，这样的时间复杂度是 O(len(T) * maxD(Trie)) 即字符串长度乘以字典树的深度

KMP 的思想很重要

显然，匹配失败并不需要在下一位置从 Trie 根节点开始匹配，而是应该找当前匹配的最长后缀。

这里引入 fail 指针的概念，表示从该节点取前缀，在字典树中找到该前缀中后缀最长的节点。
以下摘自洛谷日报

  • 共同点-两者同样是在失配的时候用于跳转的指针。
  • 不同点-KMP 要求的是最长相同真前后缀，而 AC 自动机只需要相同后缀即可。
  • 因为 KMP 只对一个模式串做匹配，而 AC 自动机要对多个模式串做匹配。
  • 有可能 fail 指针指向的结点对应着另一个模式串，两者前缀不同。
  • 也就是说，AC 自动机在对匹配串做逐位匹配时，同一位上可能匹配多个模式串。
  • 因此 fail 指针会在字典树上的结点来回穿梭，而不像 KMP 在线性结构上跳转。

构建基础思想

  • 构建一个节点的 fail 指针，需要找它的父节点的 fail 指针，所以构建过程应该是一个对树 BFS 的过程
  • 使用队列进行 BFS，每次取队首的节点，设为当前节点 cur，（该节点的 fail 指针已经构建），遍历它所有边，现假设有以字符 x 连接的子节点 child
    • 找当前节点 cur 的 fail 指针指向的节点是否也有以字符 x 连接的子节点，如果有，令 child 的 fail 指针指向该子节点
    • 如果没有，则令 cur = cur.fail，循环这个过程，直到 cur 指向 -1

查询思想

构建了 ac 自动机这种结构，它的基础应用就是给你一个字符串，让你统计在这个串中出现了多少统计的单词，而这个求解过程是在 O(N) 的复杂度下完成的

方法很简单，维护两个指针 cur 和 pos，分别指向字典树的节点和字符串遍历位置

对于每个位置 pos

  • 如果当前 cur = -1，说明该字符位置无法匹配任何模式串，则令 cur = 0， pos++
  • 如果当前 cur 位置的 cnt 计数不为 0，则将从该点及从该点可跳转的后缀纳入统计
  • 判断当前节点有否有以字符 str[pos]连接的子节点，如果有 pos++，cur 移动到该子节点的位置
  • 否则，cur 指向 cur 节点的 fail 指针的位置

代码实现

以下为 luogu P3808 的代码

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 7;
struct aho
{
    int size;
    struct node
    {
        int next[26];
        int fail, cnt;
        node()
        {
            memset(next, 0, sizeof(next));
            fail = cnt = 0;
        }
    } treeNode[maxn];
    queue<int> q;
    void init()
    {
        while (!q.empty())
        {
            q.pop();
        }
        for (int i = 0; i < maxn; ++i)
        {
            memset(treeNode[i].next, 0, sizeof(treeNode[i].next));
            treeNode[i].fail = treeNode[i].cnt = 0;
        }
        size = 0;
    }
    void insert(string s)
    {
        int cur = 0;
        for (int i = 0; i < s.length(); ++i)
        {
            int num = s[i] - 'a';
            if (!treeNode[cur].next[num])
            {
                treeNode[cur].next[num] = ++size;
            }
            cur = treeNode[cur].next[num];
        }
        treeNode[cur].cnt++;
    }

    void build()
    {
        treeNode[0].fail = -1;
        queue<int> q;
        q.push(0);
        while (!q.empty())
        {
            int top = q.front();
            q.pop();
            for (int i = 0; i < 26; ++i)
            {
                if (treeNode[top].next[i])
                {
                    q.push(treeNode[top].next[i]);
                    if (top == 0)
                    {
                        treeNode[treeNode[top].next[i]].fail = 0;
                    }
                    else
                    {

                        int v = treeNode[top].fail;
                        while (v != -1)
                        {

                            if (treeNode[v].next[i])
                            {
                                treeNode[treeNode[top].next[i]].fail = treeNode[v].next[i];
                                break;
                            }
                            else
                            {
                                v = treeNode[v].fail;
                            }
                        }
                        if (v == -1)
                        {
                            treeNode[treeNode[top].next[i]].fail = 0;
                        }
                    }
                }
            }
        }
    }

    int getNow(int cur)
    {
        int ret = 0;
        while (cur != -1)
        {
            ret += treeNode[cur].cnt;
            treeNode[cur].cnt = 0;
            cur = treeNode[cur].fail;
        }
        return ret;
    }

    int find(string target)
    {
        int res = 0;
        int pos = 0, cur = 0;
        while (pos < target.length())
        {
            if (treeNode[cur].cnt)
            {
                res += getNow(cur);
            }
            int num = target[pos] - 'a';
            if (cur == -1)
            {
                ++pos;
                cur = 0;
            }
            else if (treeNode[cur].next[num])
            {
                ++pos;
                cur = treeNode[cur].next[num];
            }
            else
            {
                cur = treeNode[cur].fail;
            }
        }
        if (treeNode[cur].cnt)
        {
            res += getNow(cur);
        }
        return res;
    }
    // 用来检查构建的字典树和fail指针的指向
    void check()
    {
        int cur = 0;
        struct pair
        {
            int v;
            string word;
            pair(int v, string word) : v(v), word(word){};
        };
        queue<pair> q;
        q.push(pair(0, ""));
        while (!q.empty())
        {
            pair top = q.front();
            q.pop();
            for (int i = 0; i < 26; ++i)
            {
                if (treeNode[top.v].next[i])
                {

                    string word = top.word + char('a' + i);
                    q.push(pair(treeNode[top.v].next[i], word));
                    cout << "开始输出节点信息" << endl;
                    cout << "当前节点为编号" << treeNode[top.v].next[i] << endl;
                    cout << "word=" << word << endl;
                    cout << "cnt=" << treeNode[treeNode[top.v].next[i]].cnt << endl;
                    cout << "fail=" << treeNode[treeNode[top.v].next[i]].fail << endl;
                    cout << "节点信息输出完毕" << endl;
                }
            }
        }
    }
};
int main()
{
    freopen("3808.in", "r", stdin);
    int n;
    cin >> n;
    aho a;
    a.init();
    for (int i = 0; i < n; ++i)
    {
        string t;
        cin >> t;
        a.insert(t);
    }
    a.build();
    // a.check();
    string target;
    cin >> target;
    cout << a.find(target);
}