This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/abc268/tasks/abc268_Ex" #include <iostream> #include "library/string/aho_corasick_array.hpp" int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::string s; std::cin >> s; int n; std::cin >> n; suisen::AhoCorasickArray<26, 'a'> ac; for (int i = 0; i < n; ++i) { std::string t; std::cin >> t; ac.add(t); } ac.build(); int ans = 0; int state = ac.init_state(); for (char c : s) { if (int next_state = ac.next_state(state, c); ac.count_suffix_matching(next_state)) { ++ans; state = ac.init_state(); } else { state = next_state; } } std::cout << ans << std::endl; return 0; }
#line 1 "test/src/string/aho_corasick_array/abc268_h.test.cpp" #define PROBLEM "https://atcoder.jp/contests/abc268/tasks/abc268_Ex" #include <iostream> #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 #line 6 "test/src/string/aho_corasick_array/abc268_h.test.cpp" int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::string s; std::cin >> s; int n; std::cin >> n; suisen::AhoCorasickArray<26, 'a'> ac; for (int i = 0; i < n; ++i) { std::string t; std::cin >> t; ac.add(t); } ac.build(); int ans = 0; int state = ac.init_state(); for (char c : s) { if (int next_state = ac.next_state(state, c); ac.count_suffix_matching(next_state)) { ++ans; state = ac.init_state(); } else { state = next_state; } } std::cout << ans << std::endl; return 0; }