結果

問題 No.430 文字列検索
コンテスト
ユーザー ああ
提出日時 2026-06-04 21:32:39
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 2,685 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,231 ms
コンパイル使用メモリ 174,580 KB
実行使用メモリ 10,672 KB
最終ジャッジ日時 2026-06-04 21:32:43
合計ジャッジ時間 2,891 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <deque>
#define rep(n, i) for (int i = 0; i < n; i++)
using namespace std;

template <char start = 'a', char end = 'z'>
struct Aho {
    static constexpr int size = end - start + 1;
    struct node {
        bool term;
        int fail;
        int in;
        int nxt[size];
        int move[size];
    };
    vector<node> nodes = {node{}};
    vector<int> ids;
    vector<int> cnt;
    void add(const string& s) {
        int cur = 0;
        for (auto c: s) {
            if (nodes[cur].nxt[c - start] == 0) {
                nodes.push_back(node{});
                nodes[cur].nxt[c - start] = nodes.size() - 1;
            }
            cur = nodes[cur].nxt[c - start];
        }
        nodes[cur].term = true;
        ids.push_back(cur);
    }
    void init() {
        deque<int> que;
        rep(size, i) {
            int nxt = nodes[0].nxt[i];
            if (nxt != 0) {
                nodes[0].move[i] = nxt;
                nodes[0].in++;
                nodes[nxt].fail = 0;
                que.push_back(nxt);
            }
        }
        while (!que.empty()) {
            int u = que.front();
            que.pop_front();
            rep(size, i) {
                nodes[u].move[i] = nodes[nodes[u].fail].move[i];
                int nxt = nodes[u].nxt[i];
                if (nxt != 0) {
                    nodes[u].move[i] = nxt;
                    int fail = nodes[nodes[u].fail].move[i];
                    nodes[nxt].fail = fail;
                    nodes[fail].in++;
                    que.push_back(nxt);
                }
            }
        }
    }
    void search(const string& s) {
        cnt = vector(nodes.size(), 0);
        int cur = 0;
        for (auto c: s) {
            cur = nodes[cur].move[c - start];
            cnt[cur]++;
        }
        vector<int> que;
        vector<int> tin(nodes.size());
        rep(nodes.size(), i) {
            tin[i] = nodes[i].in;
            if (tin[i] == 0) {
                que.push_back(i);
            }
        }
        while (!que.empty()) {
            int u = que.back();
            que.pop_back();
            int nxt = nodes[u].fail;
            cnt[nxt] += cnt[u];
            tin[nxt]--;
            if (tin[nxt] == 0) {
                que.push_back(nxt);
            }
        }
    }
    int count(int id) {
        return cnt[ids[id]];
    }
};

int main() {
    string s;
    int m;
    cin >> s >> m;
    Aho<'A', 'Z'> aho;
    rep(m, i) {
        string c;
        cin >> c;
        aho.add(c);
    }
    aho.init();
    aho.search(s);
    int ans = 0;
    rep(m, i) {
        ans += aho.count(i);
    }
    cout << ans << endl;
}
0