2023-10-24随笔

　　今天上午花了点时间写了牛客上的一道AC自动机的题，上次看到一篇讲AC自动机的文章之后只是花了些时间先去复习了KMP算法，然后写了KMP的题，AC自动机倒是没试过。不过算法思路大致记得，琢磨了一番终于正确敲出代码了。但是懒得发文章来讲解了，感觉意义不大，想学的人会找到更好的资料，不想学的不会来看的。我就把我的解题代码给贴出来吧。

　　牛客-TJOI2013，我的解法用到的知识点有：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
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
#include <list>
#include <queue>
#include <string>
#include <iostream>
#include <unordered_map>
using namespace std;
string words[205];
int wordsNum = 0;

class Node
{
public:
    Node *next[128] = {nullptr};
    Node *fail = nullptr;
    Node *father = nullptr;
    bool flag = false;
    int count = 0; // 被统计的次数
};

Node *root = nullptr;
unordered_map<Node *, Node *> last; // Node通过fail递归查询得到的第一个具有flag的Node节点，初始状态应该指向其fail

void Init()
{
    cin >> wordsNum;
    for (int i = 0; i < wordsNum; ++i)
    {
        cin >> words[i];
    }
    /* Start building AC automaton */
    root = new Node;
    Node *ptr = nullptr;

    /* Build trie first */
    for (int i = 0; i < wordsNum; ++i)
    {
        ptr = root;
        string &str = words[i];
        for (char &c : str)
        {
            if (nullptr == ptr->next[c])
            {
                ptr->next[c] = new Node;
                ptr->next[c]->father = ptr;
            }
            ptr = ptr->next[c];
        }
        ptr->flag = true;
    }

    /* Now we can build AC automaton */
    queue<Node *> que;
    Node *tmp = nullptr;
    que.push(root);
    while (!que.empty())
    {
        ptr = que.front();
        que.pop();
        for (int i = 0; i < 128; ++i)
        {
            if (!ptr->next[i])
                continue;
            ptr->next[i]->fail = root;
            tmp = ptr->fail;
            while (tmp)
            {
                if (tmp->next[i])
                {
                    ptr->next[i]->fail = tmp->next[i];
                    break;
                }
                else
                {
                    tmp = tmp->fail;
                }
            }
            que.push(ptr->next[i]);
        }
        last[ptr] = ptr->fail;
        // printf("last[%p]=%p\n", ptr, last[ptr]);
    }
}

Node *FindFlagNodeByFail(Node *ptr)
{
    if (!ptr || !ptr->fail)
    {
        return nullptr;
    }
    if (last[ptr] && last[ptr]->flag)
    {
        return last[ptr];
    }
    else
    {
        return last[ptr] = FindFlagNodeByFail(last[ptr]);
    }
}

Node *GetNodeByWord(string &str)
{
    Node *ptr = root;
    for (char &c : str)
        ptr = ptr->next[c];
    return ptr;
}

int main()
{
    Init();
    Node *ptr = nullptr;
    Node *tmp = nullptr;
    for (int i = 0; i < wordsNum; ++i)
    {
        ptr = root;
        for (char &c : words[i])
        {
            if (!ptr->next[c])
            {
                continue;
            }
            ptr = ptr->next[c];
            tmp = ptr;
            do
            {
                // printf("tmp = %p\n", tmp);
                if (tmp->flag)
                {
                    tmp->count++;
                    // printf("i = %d, %p->count++\n", i, tmp);
                }
                tmp = FindFlagNodeByFail(tmp);
            } while (tmp);
        }
    }
    for (int i = 0; i < wordsNum; ++i)
    {
        Node *node = GetNodeByWord(words[i]);
        cout << node->count << '\n';
    }
}
随笔
2023-10-24随笔
https://mxx23.github.io/2023/10/24/2023-10-24随笔/
作者
mxx
发布于
2023年10月24日
许可协议