#837906 (C++17) No.430 文字列検索

• 問題: No.430 文字列検索
• ユーザー: kuhaku
• 提出日時: 2023-02-06 13:33:34
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 9 ms / 2,000 ms
• コード長: 7,009 bytes
• コンパイル時間: 3,456 ms
• コンパイル使用メモリ: 228,176 KB
• 実行使用メモリ: 6,068 KB
• 最終ジャッジ日時: 2023-09-18 01:14:28
• 合計ジャッジ時間: 4,508 ms
• ジャッジサーバーID （参考情報）: judge11 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,376 KB
testcase_01	AC	9 ms; 6,068 KB
testcase_02	AC	4 ms; 4,376 KB
testcase_03	AC	3 ms; 4,380 KB
testcase_04	AC	2 ms; 4,380 KB
testcase_05	AC	2 ms; 4,376 KB
testcase_06	AC	2 ms; 4,376 KB
testcase_07	AC	2 ms; 4,380 KB
testcase_08	AC	2 ms; 4,376 KB
testcase_09	AC	2 ms; 4,376 KB
testcase_10	AC	2 ms; 4,380 KB
testcase_11	AC	8 ms; 5,200 KB
testcase_12	AC	9 ms; 5,436 KB
testcase_13	AC	9 ms; 5,408 KB
testcase_14	AC	7 ms; 4,944 KB
testcase_15	AC	5 ms; 4,416 KB
testcase_16	AC	5 ms; 4,396 KB
testcase_17	AC	5 ms; 4,412 KB

ソースコード

#line 1 "a.cpp"
#define PROBLEM ""
#line 2 "/home/kuhaku/home/github/algo/lib/template/template.hpp"
#pragma GCC target("sse4.2,avx2,bmi2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
bool chmax(T &a, const U &b) {
    return a < (T)b ? a = (T)b, true : false;
}
template <class T, class U>
bool chmin(T &a, const U &b) {
    return (T)b < a ? a = (T)b, true : false;
}
constexpr int64_t INF = 1000000000000000003;
constexpr int Inf = 1000000003;
constexpr int MOD = 1000000007;
constexpr int MOD_N = 998244353;
constexpr double EPS = 1e-7;
constexpr double PI = M_PI;
#line 3 "/home/kuhaku/home/github/algo/lib/template/macro.hpp"
#define FOR(i, m, n) for (int i = (m); i < int(n); ++i)
#define FORR(i, m, n) for (int i = (m)-1; i >= int(n); --i)
#define FORL(i, m, n) for (int64_t i = (m); i < int64_t(n); ++i)
#define rep(i, n) FOR (i, 0, n)
#define repn(i, n) FOR (i, 1, n + 1)
#define repr(i, n) FORR (i, n, 0)
#define repnr(i, n) FORR (i, n + 1, 1)
#define all(s) (s).begin(), (s).end()
#line 3 "/home/kuhaku/home/github/algo/lib/template/sonic.hpp"
struct Sonic {
    Sonic() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }

    constexpr void operator()() const {}
} sonic;
#line 5 "/home/kuhaku/home/github/algo/lib/template/atcoder.hpp"
using ll = int64_t;
using ld = long double;
template <class T, class U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    return is >> p.first >> p.second;
}
template <class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (T &i : v) is >> i;
    return is;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for (auto it = v.begin(); it != v.end(); ++it) {
        os << (it == v.begin() ? "" : " ") << *it;
    }
    return os;
}
template <class Head, class... Tail>
void co(Head &&head, Tail &&...tail) {
    if constexpr (sizeof...(tail) == 0) std::cout << head << '\n';
    else std::cout << head << ' ', co(std::forward<Tail>(tail)...);
}
template <class Head, class... Tail>
void ce(Head &&head, Tail &&...tail) {
    if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n';
    else std::cerr << head << ' ', ce(std::forward<Tail>(tail)...);
}
template <typename T, typename... Args>
auto make_vector(T x, int arg, Args... args) {
    if constexpr (sizeof...(args) == 0) return std::vector<T>(arg, x);
    else return std::vector(arg, make_vector<T>(x, args...));
}
void setp(int n) {
    std::cout << std::fixed << std::setprecision(n);
}
void Yes(bool is_correct = true) {
    std::cout << (is_correct ? "Yes" : "No") << '\n';
}
void No(bool is_not_correct = true) {
    Yes(!is_not_correct);
}
void YES(bool is_correct = true) {
    std::cout << (is_correct ? "YES" : "NO") << '\n';
}
void NO(bool is_not_correct = true) {
    YES(!is_not_correct);
}
void Takahashi(bool is_correct = true) {
    std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n';
}
void Aoki(bool is_not_correct = true) {
    Takahashi(!is_not_correct);
}
#line 3 "a.cpp"

template <int char_size, int base>
struct aho_corasick {
  private:
    struct _node {
        std::vector<int> next_node;
        _node() : next_node(char_size, -1) {}

        int next(int x) const {
            return this->next_node[x];
        }
    };

  public:
    using node_type = _node;

    aho_corasick() : nodes(), correct(), failure() {
        this->nodes.emplace_back();
        this->correct.emplace_back();
    }

    int size() const noexcept {
        return this->nodes.size();
    }

    void build() {
        this->failure = std::vector<int>(this->nodes.size(), 0);
        std::queue<int> que;
        for (int i = 0; i < char_size; ++i) {
            int next_root = this->nodes[0].next(i);
            if (next_root != -1) {
                que.emplace(next_root);
            }
        }

        while (!que.empty()) {
            int x = que.front();
            que.pop();
            for (int i = 0; i < char_size; ++i) {
                int next_x = this->nodes[x].next(i);
                if (next_x == -1)
                    continue;
                que.emplace(next_x);
                int y = x;
                do {
                    y = this->failure[y];
                    int next_y = this->nodes[y].next(i);
                    if (next_y != -1) {
                        this->failure[next_x] = next_y;
                        this->correct[next_x] += this->correct[next_y];
                        break;
                    }
                } while (y != 0);
            }
        }
    }

    void insert(const std::string &word) {
        int node_id = 0;
        for (int i = 0; i < (int)word.size(); ++i) {
            int c = word[i] - base;
            int &next_id = this->nodes[node_id].next_node[c];
            if (next_id == -1) {
                next_id = this->nodes.size();
                this->nodes.emplace_back();
                this->correct.emplace_back();
            }
            node_id = next_id;
        }
        this->correct[node_id]++;
    }

    int search_id(const std::string &word) {
        int node_id = 0;
        for (int i = 0; i < (int)word.size(); ++i) {
            int c = word[i] - base;
            int &next_id = this->nodes[node_id].next_node[c];
            if (next_id == -1)
                return -1;
            node_id = next_id;
        }
        return node_id;
    }

    node_type get_node(int node_id) const {
        assert(0 <= node_id && node_id < (int)this->nodes.size());
        return this->nodes[node_id];
    }

    std::pair<int64_t, int> move(const char c, int now = 0) {
        int next_id = this->nodes[now].next(c - base);
        while (next_id == -1 && now != 0) {
            now = this->failure[now];
            next_id = this->nodes[now].next(c - base);
        }
        return next_id != -1 ? std::pair<int64_t, int>{this->correct[next_id], next_id}
                             : std::pair<int64_t, int>{0, 0};
    }

    std::pair<int64_t, int> move(const std::string &str, int now = 0) {
        int64_t sum = 0;
        for (auto &c : str) {
            auto nxt = move(c, now);
            sum += nxt.first;
            now = nxt.second;
        }
        return {sum, now};
    }

    std::vector<int> get_correct() {
        return this->correct;
    }

    std::vector<int> get_failure() {
        return this->failure;
    }

  private:
    std::vector<node_type> nodes;
    std::vector<int> correct;
    std::vector<int> failure;
};

int main(void) {
    string s;
    cin >> s;
    int m;
    cin >> m;
    aho_corasick<26, 'A'> aho;
    rep (i, m) {
        string t;
        cin >> t;
        aho.insert(t);
    }
    aho.build();
    co(aho.move(s).first);

    return 0;
}