test/yukicoder/430.test.cpp

View this file on GitHub
Last update: 2026-10-27 07:43:44+09:00
Problem: https://yukicoder.me/problems/no/430

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/430"
#include <iostream>
#include <string>

#include "string/aho_corasick.hpp"
#include "string/trie.hpp"
int main() {
    std::string s;
    int m;
    std::cin >> s >> m;
    trie<26, 'A'> t;
    for (int i = 0; i < m; i++) {
        std::string c;
        std::cin >> c;
        t.insert(c);
    }
    aho_corasick ac(t);
    long long ans = 0;
    int v = 0;
    for (char ch : s) {
        v = ac.next(v, ch);
        ans += ac.count(v);
    }
    std::cout << ans << '\n';
}

#line 1 "test/yukicoder/430.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/430"
#include <iostream>
#include <string>

#line 2 "string/aho_corasick.hpp"
#include <array>
#include <cassert>
#include <vector>

#line 5 "string/trie.hpp"
template <int sigma = 26, int base = 'a'> struct trie {
    static_assert(sigma >= 1);

public:
    trie() : ch(1), par(1, -1), dep(1, 0), cnt(1, 0), cnt_prefix(1, 0) {
        ch[0].fill(-1);
    }
    int size() const {
        return int(ch.size());
    }
    template <class Seq> int insert(const Seq& s) {
        int v = 0;
        cnt_prefix[v]++;
        for (auto c : s) {
            int x = int(c) - base;
            assert(0 <= x && x < sigma);
            if (ch[v][x] == -1) {
                ch[v][x] = size();
                ch.emplace_back().fill(-1);
                par.push_back(v);
                dep.push_back(dep[v] + 1);
                cnt.push_back(0);
                cnt_prefix.push_back(0);
            }
            v = ch[v][x];
            cnt_prefix[v]++;
        }
        cnt[v]++;
        return v;
    }
    template <class Seq> void erase(const Seq& s) {
        int t = find(s);
        assert(t != -1 && cnt[t] > 0);
        cnt[t]--;
        for (int v = t; v != -1; v = par[v]) cnt_prefix[v]--;
    }
    template <class Seq> int find(const Seq& s) const {
        int v = 0;
        for (auto c : s) {
            v = next(v, int(c));
            if (v == -1) return -1;
        }
        return v;
    }
    int next(int v, int c) const {
        assert(0 <= v && v < size());
        int x = c - base;
        assert(0 <= x && x < sigma);
        return ch[v][x];
    }
    int parent(int v) const {
        assert(0 <= v && v < size());
        return par[v];
    }
    int depth(int v) const {
        assert(0 <= v && v < size());
        return dep[v];
    }
    int count(int v) const {
        assert(0 <= v && v < size());
        return cnt[v];
    }
    int count_prefix(int v) const {
        assert(0 <= v && v < size());
        return cnt_prefix[v];
    }

private:
    std::vector<std::array<int, sigma>> ch;
    std::vector<int> par, dep, cnt, cnt_prefix;
};
#line 7 "string/aho_corasick.hpp"
template <int sigma = 26, int base = 'a'> struct aho_corasick {
    explicit aho_corasick(const trie<sigma, base>& t) : _n(t.size()), nxt(_n), fl(_n, -1), cnt(_n) {
        ord.reserve(_n);
        ord.push_back(0);
        for (int i = 0; i < _n; i++) {
            int v = ord[i];
            cnt[v] = t.count(v) + (v == 0 ? 0 : cnt[fl[v]]);
            for (int c = 0; c < sigma; c++) {
                int w = t.next(v, base + c);
                if (w == -1) {
                    nxt[v][c] = v == 0 ? 0 : nxt[fl[v]][c];
                } else {
                    nxt[v][c] = w;
                    fl[w] = v == 0 ? 0 : nxt[fl[v]][c];
                    ord.push_back(w);
                }
            }
        }
        assert(int(ord.size()) == _n);
    }
    int size() const {
        return _n;
    }
    int next(int v, int c) const {
        assert(0 <= v && v < _n);
        int x = c - base;
        assert(0 <= x && x < sigma);
        return nxt[v][x];
    }
    int fail(int v) const {
        assert(0 <= v && v < _n);
        return fl[v];
    }
    int count(int v) const {
        assert(0 <= v && v < _n);
        return cnt[v];
    }
    const std::vector<int>& order() const {
        return ord;
    }

  private:
    int _n;
    std::vector<std::array<int, sigma>> nxt;
    std::vector<int> fl, cnt, ord;
};
#line 7 "test/yukicoder/430.test.cpp"
int main() {
    std::string s;
    int m;
    std::cin >> s >> m;
    trie<26, 'A'> t;
    for (int i = 0; i < m; i++) {
        std::string c;
        std::cin >> c;
        t.insert(c);
    }
    aho_corasick ac(t);
    long long ans = 0;
    int v = 0;
    for (char ch : s) {
        v = ac.next(v, ch);
        ans += ac.count(v);
    }
    std::cout << ans << '\n';
}