test/src/string/aho_corasick/abc268_h.test.cpp

• View this file on GitHub
• Last update: 2023-01-01 18:21:45+09:00
• Problem: https://atcoder.jp/contests/abc268/tasks/abc268_Ex

Depends on

• Aho Corasick (library/string/aho_corasick.hpp)

Code

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

#include <iostream>

#include "library/string/aho_corasick.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::AhoCorasick 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/abc268_h.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc268/tasks/abc268_Ex"

#include <iostream>

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



#include <cassert>
#include <deque>
#include <map>
#include <vector>

namespace suisen {
    template <typename T = char>
    struct AhoCorasick {
        using value_type = T;

        AhoCorasick() : _next(1) {}

        template <typename Container, std::enable_if_t<std::is_constructible_v<value_type, typename Container::value_type>, std::nullptr_t> = nullptr>
        void add(const Container& s) {
            int cur = init_state();
            for (value_type c : s) {
                auto [it, inserted] = _next[cur].try_emplace(c, _next.size());
                if (inserted) _next.emplace_back();
                cur = it->second;
            }
            _marks.push_back(cur);
            _built = false;
        }

        void build() {
            _built = true;
            const int n = _next.size();
            _failure.resize(n, 0);
            _count.resize(n, 0);
            for (int mark : _marks) ++_count[mark];
            std::deque<int> dq{ 0 };
            while (dq.size()) {
                const int cur = dq.front();
                dq.pop_front();
                for (const auto& [c, nxt] : _next[cur]) {
                    if (cur) {
                        _failure[nxt] = next_state(_failure[cur], c);
                        _count[nxt] += _count[_failure[nxt]];
                    }
                    dq.push_back(nxt);
                }
            }
        }

        int init_state() const {
            return 0;
        }
        int next_state(int state, value_type c) const {
            assert(_built);
            while (true) {
                if (auto it = _next[state].find(c); it == _next[state].end()) {
                    if (state == 0) return 0;
                    state = _failure[state];
                } else {
                    return it->second;
                }
            }
        }
        int count_suffix_matching(int state) const {
            assert(_built);
            return _count[state];
        }
    private:
        std::vector<int> _failure;
        std::vector<std::map<value_type, int>> _next;
        std::vector<int> _marks;
        std::vector<int> _count;
        bool _built = true;
    };
} // namespace suisen



#line 6 "test/src/string/aho_corasick/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::AhoCorasick 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