cp-library-cpp

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

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

:heavy_check_mark: test/src/string/aho_corasick_array/abc268_h.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc268/tasks/abc268_h"

#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_h"

#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;
}
Back to top page