String/Trie.hpp

• View this file on GitHub
• Last update: 2023-02-11 22:28:05+08:00
• Include: #include "String/Trie.hpp"

Depends on

• Template/Template.hpp

Required by

• String/ACAutomaton.hpp

Verified with

• Verify/ACAutomaton.test.cpp

Code

#pragma once
#include "../Template/Template.hpp"

// struct TrieNode {
//     TrieNode() { id = 0, dep = 0, nxt = std::array<int, 26>(); };
//     TrieNode(int _id, int _dep) : id(_id), dep(_dep) {}
//     int id;
//     int dep;
//     std::array<int, 26> nxt = {};
//     int &operator[](const int x) { return this->nxt[x]; }
// };
template <class Node>
struct trie {
    std::vector<Node> tr;
    trie() { tr.push_back(Node()); };

    int add(const std::string &s) {
        int n = s.size();
        int p = 0;
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'A';
            if (!tr[p][c]) {
                tr[p][c] = tr.size();
                tr.emplace_back(tr[p][c], tr[p].dep + 1);
            }
            p = tr[p][c];
        }
        return p;
    }

    int size() const { return tr.size(); }
};

#line 2 "Template/Template.hpp"

#include <bits/stdc++.h>

using i64 = std::int64_t;
#line 3 "String/Trie.hpp"

// struct TrieNode {
//     TrieNode() { id = 0, dep = 0, nxt = std::array<int, 26>(); };
//     TrieNode(int _id, int _dep) : id(_id), dep(_dep) {}
//     int id;
//     int dep;
//     std::array<int, 26> nxt = {};
//     int &operator[](const int x) { return this->nxt[x]; }
// };
template <class Node>
struct trie {
    std::vector<Node> tr;
    trie() { tr.push_back(Node()); };

    int add(const std::string &s) {
        int n = s.size();
        int p = 0;
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'A';
            if (!tr[p][c]) {
                tr[p][c] = tr.size();
                tr.emplace_back(tr[p][c], tr[p].dep + 1);
            }
            p = tr[p][c];
        }
        return p;
    }

    int size() const { return tr.size(); }
};

Back to top page