結果

問題 No.430 文字列検索
ユーザー SnowBeenDidingSnowBeenDiding
提出日時 2024-08-10 04:18:12
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 4,937 bytes
コンパイル時間 3,410 ms
コンパイル使用メモリ 265,184 KB
実行使用メモリ 7,780 KB
最終ジャッジ日時 2024-11-10 01:12:05
合計ジャッジ時間 3,486 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 15 ms
7,780 KB
testcase_02 AC 7 ms
5,248 KB
testcase_03 AC 7 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 4 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 12 ms
6,120 KB
testcase_12 AC 13 ms
6,364 KB
testcase_13 AC 13 ms
6,504 KB
testcase_14 AC 11 ms
5,704 KB
testcase_15 AC 9 ms
5,708 KB
testcase_16 AC 9 ms
5,708 KB
testcase_17 AC 8 ms
5,704 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace std;

typedef long long ll;

template <int char_size> struct TrieNode {
    int nxt[char_size];

    int exist;
    vector<int> accept;

    TrieNode() : exist(0) { memset(nxt, -1, sizeof(nxt)); }
};

template <int char_size, int margin> struct Trie {
    // https://ei1333.github.io/luzhiled/snippets/structure/trie.html
    using Node = TrieNode<char_size>;

    vector<Node> nodes;
    int root;

    Trie() : root(0) { nodes.push_back(Node()); }

    void update_direct(int node, int id) { nodes[node].accept.push_back(id); }

    void update_child(int node, int child, int id) { ++nodes[node].exist; }

    void add(const string &str, int str_index, int node_index, int id) {
        if (str_index == str.size()) {
            update_direct(node_index, id);
        } else {
            const int c = str[str_index] - margin;
            if (nodes[node_index].nxt[c] == -1) {
                nodes[node_index].nxt[c] = (int)nodes.size();
                nodes.push_back(Node());
            }
            add(str, str_index + 1, nodes[node_index].nxt[c], id);
            update_child(node_index, nodes[node_index].nxt[c], id);
        }
    }

    void add(const string &str, int id) { add(str, 0, 0, id); }

    void add(const string &str) { add(str, nodes[0].exist); }

    void query(const string &str, const function<void(int)> &f, int str_index,
               int node_index) {
        for (auto &idx : nodes[node_index].accept)
            f(idx);
        if (str_index == str.size()) {
            return;
        } else {
            const int c = str[str_index] - margin;
            if (nodes[node_index].nxt[c] == -1)
                return;
            query(str, f, str_index + 1, nodes[node_index].nxt[c]);
        }
    }

    void query(const string &str, const function<void(int)> &f) {
        query(str, f, 0, 0);
    }

    int count() const { return (nodes[0].exist); }

    int size() const { return ((int)nodes.size()); }
};

template <int char_size, int margin>
struct AhoCorasick : Trie<char_size + 1, margin> {
    // https://ei1333.github.io/library/string/aho-corasick.hpp.html
    using Trie<char_size + 1, margin>::Trie;

    const int FAIL = char_size;
    vector<int> correct;

    void build(bool heavy = true) {
        correct.resize(this->size());
        for (int i = 0; i < this->size(); i++) {
            correct[i] = (int)this->nodes[i].accept.size();
        }
        queue<int> que;
        for (int i = 0; i <= char_size; i++) {
            if (~this->nodes[0].nxt[i]) {
                this->nodes[this->nodes[0].nxt[i]].nxt[FAIL] = 0;
                que.emplace(this->nodes[0].nxt[i]);
            } else {
                this->nodes[0].nxt[i] = 0;
            }
        }
        while (!que.empty()) {
            auto &now = this->nodes[que.front()];
            int fail = now.nxt[FAIL];
            correct[que.front()] += correct[fail];
            que.pop();
            for (int i = 0; i < char_size; i++) {
                if (~now.nxt[i]) {
                    this->nodes[now.nxt[i]].nxt[FAIL] =
                        this->nodes[fail].nxt[i];
                    if (heavy) {
                        auto &u = this->nodes[now.nxt[i]].accept;
                        auto &v = this->nodes[this->nodes[fail].nxt[i]].accept;
                        vector<int> accept;
                        set_union(begin(u), end(u), begin(v), end(v),
                                  back_inserter(accept));
                        u = accept;
                    }
                    que.emplace(now.nxt[i]);
                } else {
                    now.nxt[i] = this->nodes[fail].nxt[i];
                }
            }
        }
    }

    unordered_map<int, int> match(const string &str, int now = 0) {
        unordered_map<int, int> result, visit_cnt;
        for (auto &c : str) {
            now = this->nodes[now].nxt[c - margin];
            visit_cnt[now]++;
        }
        for (auto &[now, cnt] : visit_cnt) {
            for (auto &v : this->nodes[now].accept)
                result[v] += cnt;
        }
        return result;
    }

    pair<int64_t, int> move(const char &c, int now = 0) {
        now = this->nodes[now].nxt[c - margin];
        return {correct[now], now};
    }

    pair<int64_t, int> move(const 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};
    }
};

int main() {
    string s;
    int q;
    cin >> s >> q;
    AhoCorasick<26, 'A'> aho;
    rep(i, 0, q) {
        string t;
        cin >> t;
        aho.add(t);
    }
    aho.build();
    auto res = aho.match(s);
    ll ans = 0;
    for (auto &p : res) {
        ans += p.second;
    }
    cout << ans << endl;
}
0