結果

問題 No.430 文字列検索
ユーザー downer
提出日時 2025-02-16 03:12:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 2,342 bytes
コンパイル時間 3,462 ms
コンパイル使用メモリ 289,628 KB
実行使用メモリ 11,036 KB
最終ジャッジ日時 2025-02-16 03:12:57
合計ジャッジ時間 4,539 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/no/430"

#include <bits/stdc++.h>
using namespace std;

template <int ALPHA_SIZE=26>
struct AhoCorasick {
    struct Node {
        vector<Node*> children;
        Node* fail;
        vector<int> output;
        Node() : children(ALPHA_SIZE, nullptr), fail(nullptr) {}
    };

    Node* root;
    vector<string> patterns;

    AhoCorasick() : root(new Node()) {}

    void insert(const string& word, int index) {
        Node* cur = root;
        for(char c : word) {
            int idx = c - 'a';
            if(cur->children[idx] == nullptr) cur->children[idx] = new Node();
            cur = cur->children[idx];
        }
        cur->output.push_back(index);
    }

    void build() {
        queue<Node*> q;
        root->fail = root;
        for(int i = 0; i < ALPHA_SIZE; i++) {
            if(root->children[i]) {
                root->children[i]->fail = root;
                q.push(root->children[i]);
            }
            else root->children[i] = root;
        }
        while(q.size()) {
            Node* cur = q.front();
            q.pop();
            for(int i = 0; i < ALPHA_SIZE; i++) {
                Node* child = cur->children[i];
                if(child) {
                    child->fail = cur->fail->children[i];
                    child->output.insert(child->output.end(), child->fail->output.begin(), child->fail->output.end());
                    q.push(child);
                }
                else cur->children[i] = cur->fail->children[i];
            }
        }
    }

    vector<pair<int, int>> search(const string& word) {
        vector<pair<int, int>> matches;
        Node* cur = root;
        for(int i = 0; i < (int)word.size(); i++) {
            int idx = word[i] - 'a';
            cur = cur->children[idx];
            for(int pat_idx : cur->output) matches.emplace_back(i, pat_idx);
        }
        return matches;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string S;
    int M;
    cin >> S >> M;

    for(char& c : S) c += 32;

    AhoCorasick ac;
    for(int i = 0; i < M; i++) {
        string C;
        cin >> C;

        for(char& c : C) c += 32;
        
        ac.insert(C, i);
    }

    ac.build();
    auto matches = ac.search(S);
    cout << matches.size() << "\n";

    return 0;
}
0