結果

問題 No.430 文字列検索
ユーザー lowrlowr
提出日時 2019-08-09 22:34:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 165 ms / 2,000 ms
コード長 4,667 bytes
コンパイル時間 1,882 ms
コンパイル使用メモリ 211,104 KB
実行使用メモリ 9,360 KB
最終ジャッジ日時 2024-08-15 16:19:07
合計ジャッジ時間 2,851 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 165 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 9 ms
9,360 KB
testcase_03 AC 5 ms
6,940 KB
testcase_04 AC 5 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 3 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 8 ms
7,868 KB
testcase_13 AC 8 ms
8,008 KB
testcase_14 AC 9 ms
8,256 KB
testcase_15 AC 6 ms
7,704 KB
testcase_16 AC 6 ms
6,940 KB
testcase_17 AC 5 ms
6,944 KB
testcase_18 AC 6 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using i64 = long long;

namespace Trie {
    template <unsigned alphabet_size>
    struct Node {
        Node *next[alphabet_size];
        unsigned exist;
        std::vector<int> accept;

        Node() : next(), exist(0) {}
    };

    template <unsigned alphabet_size>
    class NodePool {
        unsigned pool_size;
        unsigned pos;
        std::allocator<Node<alphabet_size>> alc;
        Node<alphabet_size> *pool;

    public:
        NodePool(unsigned size) :
            pool_size(size),
            pos(0),
            pool(alc.allocate(pool_size)) {}

        ~NodePool() {
            for (unsigned i = 0; i < pos; i++) pool[pos - 1 - i].~Node();
            alc.deallocate(pool, pool_size);
        }

        auto alloc() {
            return new(pool + pos++) Node<alphabet_size>();
        }
    };

    template <unsigned alphabet_size = 26, unsigned margin = 'a'>
    struct Trie {
        NodePool<alphabet_size> pool;
        Node<alphabet_size> *root;

        void add_impl(const std::string &str, unsigned id) {
            auto node = root;
            for (unsigned c : str) {
                c -= margin;
                if (node->next[c] == nullptr) {
                    node->next[c] = pool.alloc();
                }
                node->exist++;
                node = node->next[c];
            }

            node->accept.push_back(id);
        }

        // maximum size of node pool
        explicit Trie(unsigned max_pool_size) :
            pool(max_pool_size),
            root(pool.alloc()) {}

        void add(const std::string &str) {
            add_impl(str, root->exist);
        }
    };

    template <unsigned alphabet_size = 26, unsigned margin = 'a'>
    struct AhoCorasick : Trie<alphabet_size + 2, margin> {
        using TrieF = Trie<alphabet_size + 2, margin>;
        using NodeF = Node<alphabet_size + 2>;
        using TrieF::root;
        static constexpr unsigned failure = alphabet_size;
        static constexpr unsigned prefix = failure + 1;

        AhoCorasick(unsigned max_pool_size) : TrieF(max_pool_size) {}

        // build pattern matching automaton from trie
        void build() {
            std::deque<NodeF *> q { root };
            root->next[failure] = root;

            while (!q.empty()) {
                auto node = q.front();
                q.pop_front();

                for (unsigned c = 0; c < alphabet_size; c++) {
                    if (node->next[c] == nullptr) continue;
                    q.push_back(node->next[c]);

                    auto fail_next = node->next[failure];
                    while (fail_next->next[c] == nullptr && fail_next != root) {
                        fail_next = fail_next->next[failure];
                    }
                    node->next[c]->next[failure] = fail_next->next[c] && fail_next != node ? fail_next->next[c] : root;

                    auto t = node->next[c]->next[failure];
                    node->next[c]->next[prefix] = t->accept.size() ? t : t->next[prefix];
                }
            }
        }

        auto transition(NodeF *node, unsigned c) {
            c -= margin;
            while (node->next[c] == nullptr && node != root) {
                node = node->next[failure];
            }
            return node->next[c] ? node->next[c] : node;
        }

        auto match(const std::string &str) {
            std::vector<int> ret(root->exist);
            auto node = root;
            for (unsigned c : str) {
                node = transition(node, c);
                auto t = node;
                while (t && t != root) {
                    for (auto w : t->accept) ret[w]++;
                    t = t->next[prefix];
                }
            }

            return ret;
        }

        // F: (id: unsigned, r: unsigned) -> void
        // [r - length, r)
        template <typename F>
        void match_apply(const std::string &str, const F &f) {
            auto node = root;
            for (std::size_t i = 0; i < str.size(); i++) {
                node = transition(node, str[i]);
                auto t = node;
                while (t && t != root) {
                    for (auto w : t->accept) f(w, i + 1);
                    t = t->next[prefix];
                }
            }
        }
    };
}

int main() {
    std::string s;
    int m;
    std::cin >> s >> m;
    std::vector<std::string> c(m);
    Trie::AhoCorasick<26, 'A'> ac(50000);
    for (auto &e : c) {
        std::cin >> e;
        ac.add(e);
    }

    ac.build();
    auto v = ac.match(s);

    std::cout << std::accumulate(v.begin(), v.end(), 0ll) << std::endl;

    return 0;
}
0