1
template <typename Tp>
2
using OwnPointer = std::unique_ptr<Tp>;
3
template <typename Tp>
4
using RefPointer = Tp*;
5

6
constexpr int MAXN = 6;
7
constexpr int ALPHABET = 26;
8

9
class ACAM {
10
public:
11
    explicit ACAM(const std::vector<std::string>& set) {
12
        Build(set);
13
    }
14
private:
15
    struct TrieNode {
16
        std::array<RefPointer<TrieNode>, ALPHABET> ch;
17
        RefPointer<TrieNode> fail;
18
        bool is_taboo;
19

20
        TrieNode() {
21
            ch.fill(nullptr);
22
            fail = nullptr;
23
            is_taboo = false;
24
        }
25
    };
26
    std::vector<OwnPointer<TrieNode>> node_pool;
27
    RefPointer<TrieNode> root;
28

29
    RefPointer<TrieNode> NewNode() {
30
        node_pool.emplace_back(std::make_unique<TrieNode>());
31
        return node_pool.back().get();
32
    }
33

34
    void Insert(const std::string& s) {
35
        RefPointer<TrieNode> now = root;
36
        for(const char& c : s) {
37
            int id = c-'a';
38
            if(!now->ch[id]) {
39
                now->ch[id] = NewNode();
40
            }
41
            now=now->ch[id];
42
        }
43
        now->is_taboo = true;
44
    }
45

46
    void Build(const std::vector<std::string>& set) {
47
        root = NewNode();
48
        for(const std::string &s : set) Insert(s);
49
        std::queue<RefPointer<TrieNode>> q;
50
        root->fail = root;
51
        for(int i=0;i<ALPHABET;i++) {
52
            if(root->ch[i]) {
53
                root->ch[i]->fail = root;
54
                q.push(root->ch[i]);
55
            } else root->ch[i] = root;
56
        }
57
        while(!q.empty()) {
58
            auto u = q.front(); q.pop();
59
            u->is_taboo |= u->fail->is_taboo;
60
            for(int i{0}; i < ALPHABET; i++) {
61
                if(u->ch[i]) {
62
                    u->ch[i]->fail = u->fail->ch[i];
63
                    q.push(u->ch[i]);
64
                } else u->ch[i] = u->fail->ch[i];
65
            }
66
        }
67
    }
68
public:
69
    auto Root() const -> RefPointer<TrieNode> {
70
        return root;
71
    }
72
    auto Next(RefPointer<TrieNode> u, char c) const -> RefPointer<TrieNode> {
73
        return u->ch[c-'a'];
74
    }
75
    auto IsTaboo(RefPointer<TrieNode> u) const -> bool {
76
        return u->is_taboo;
77
    }
78
    auto Size() const -> int {
79
        return node_pool.size();
80
    }
81
};