This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/string/aho_corasick_array.hpp"
#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