cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: Aho Corasick Array
(library/string/aho_corasick_array.hpp)

Aho Corasick Array

Depends on

Verified with

Code

#ifndef SUISEN_ARRAY_AHO_CORASICK
#define SUISEN_ARRAY_AHO_CORASICK

#include <array>
#include <cassert>
#include <deque>
#include <vector>

#include "library/string/trie_array.hpp"

namespace suisen {
    template <int alphabet_size, int offset>
    struct AhoCorasickArrayNode : ArrayTrieNode<alphabet_size, offset> {
        int count;
        int failure;
    };

    template <int alphabet_size, int offset>
    struct AhoCorasickArray : private ArrayTrie<AhoCorasickArrayNode<alphabet_size, offset>> {
        using base_type = ArrayTrie<AhoCorasickArrayNode<alphabet_size, offset>>;
        using node_type = typename base_type::node_type;
        using key_type = typename base_type::key_type;

        using base_type::base_type;

        template <typename Container, std::enable_if_t<std::is_constructible_v<key_type, typename Container::value_type>, std::nullptr_t> = nullptr>
        void add(const Container& s) {
            ++base_type::add(s).count;
        }

        void build() {
            this->nodes[0].failure = init_state();
            std::deque<int> dq{ init_state() };
            while (dq.size()) {
                const int cur = dq.front();
                dq.pop_front();
                const auto& links = this->nodes[this->nodes[cur].failure];
                for (int i = 0; i < alphabet_size; ++i) {
                    const int link = cur ? links[i] : init_state();
                    if (int& nxt = this->nodes[cur][i]; nxt != node_type::none) {
                        this->nodes[nxt].failure = link;
                        this->nodes[nxt].count += this->nodes[link].count;
                        dq.push_back(nxt);
                    } else {
                        nxt = link;
                    }
                }
            }
            _built = true;
        }


        int state_num() const {
            return this->nodes.size();
        }

        int init_state() const {
            return 0;
        }
        int next_state(int state, key_type c) const {
            assert(_built);
            return this->nodes[state][c - offset];
        }
        int count_suffix_matching(int state) const {
            assert(_built);
            return this->nodes[state].count;
        }
    private:
        bool _built = false;
    };

} // namespace suisen


#endif // SUISEN_ARRAY_AHO_CORASICK
#line 1 "library/string/aho_corasick_array.hpp"



#include <array>
#include <cassert>
#include <deque>
#include <vector>

#line 1 "library/string/trie_array.hpp"



#line 7 "library/string/trie_array.hpp"

namespace suisen {
    template <int _alphabet_size, int _offset>
    struct ArrayTrieNode : std::array<int, _alphabet_size> {
        using key_type = int;

        static constexpr int none = -1;
        static constexpr int alphabet_size = _alphabet_size;
        static constexpr int offset = _offset;

        ArrayTrieNode() { this->fill(none); }
    };
    template <int _alphabet_size, int _offset>
    struct ArrayTrieNodeWithParentLink : ArrayTrieNode<_alphabet_size, _offset> {
        using base_node_type = ArrayTrieNode<_alphabet_size, _offset>;
        using key_type = typename base_node_type::key_type;
        int par;
        key_type key;

        ArrayTrieNodeWithParentLink() : base_node_type() {}
        ArrayTrieNodeWithParentLink(int par, const key_type& key) : base_node_type(), par(par), key(key) {}
    };

    template <typename NodeType, std::enable_if_t<std::is_base_of_v<ArrayTrieNode<NodeType::alphabet_size, NodeType::offset>, NodeType>, std::nullptr_t> = nullptr>
    struct ArrayTrie {
        using node_type = NodeType;
        using key_type = typename node_type::key_type;

        static constexpr int none = node_type::none;
        static constexpr int alphabet_size = node_type::alphabet_size;
        static constexpr int offset = node_type::offset;

        static constexpr int root = 0;

        using base_node_type = ArrayTrieNode<alphabet_size, offset>;

        std::vector<node_type> nodes;

        ArrayTrie() {
            nodes.emplace_back();
        }

        void reserve(int capacity) {
            nodes.reserve(capacity);
        }

        template <typename Container, std::enable_if_t<std::is_constructible_v<key_type, typename Container::value_type>, std::nullptr_t> = nullptr>
        node_type& add(const Container& s, int start = 0) {
            int cur = start;
            for (key_type c : s) {
                c -= offset;
                if (nodes[cur][c] == none) {
                    nodes[cur][c] = nodes.size();
                    if constexpr (std::is_base_of_v<ArrayTrieNodeWithParentLink<alphabet_size, offset>, node_type>) {
                        nodes.emplace_back(cur, c);
                    } else {
                        nodes.emplace_back();
                    }
                }
                cur = nodes[cur][c];
            }
            return nodes[cur];
        }

        const node_type& operator[](int i) const {
            return nodes[i];
        }
        node_type& operator[](int i) {
            return nodes[i];
        }
    };
} // namespace suisen


#line 10 "library/string/aho_corasick_array.hpp"

namespace suisen {
    template <int alphabet_size, int offset>
    struct AhoCorasickArrayNode : ArrayTrieNode<alphabet_size, offset> {
        int count;
        int failure;
    };

    template <int alphabet_size, int offset>
    struct AhoCorasickArray : private ArrayTrie<AhoCorasickArrayNode<alphabet_size, offset>> {
        using base_type = ArrayTrie<AhoCorasickArrayNode<alphabet_size, offset>>;
        using node_type = typename base_type::node_type;
        using key_type = typename base_type::key_type;

        using base_type::base_type;

        template <typename Container, std::enable_if_t<std::is_constructible_v<key_type, typename Container::value_type>, std::nullptr_t> = nullptr>
        void add(const Container& s) {
            ++base_type::add(s).count;
        }

        void build() {
            this->nodes[0].failure = init_state();
            std::deque<int> dq{ init_state() };
            while (dq.size()) {
                const int cur = dq.front();
                dq.pop_front();
                const auto& links = this->nodes[this->nodes[cur].failure];
                for (int i = 0; i < alphabet_size; ++i) {
                    const int link = cur ? links[i] : init_state();
                    if (int& nxt = this->nodes[cur][i]; nxt != node_type::none) {
                        this->nodes[nxt].failure = link;
                        this->nodes[nxt].count += this->nodes[link].count;
                        dq.push_back(nxt);
                    } else {
                        nxt = link;
                    }
                }
            }
            _built = true;
        }


        int state_num() const {
            return this->nodes.size();
        }

        int init_state() const {
            return 0;
        }
        int next_state(int state, key_type c) const {
            assert(_built);
            return this->nodes[state][c - offset];
        }
        int count_suffix_matching(int state) const {
            assert(_built);
            return this->nodes[state].count;
        }
    private:
        bool _built = false;
    };

} // namespace suisen
Back to top page