結果

問題 No.430 文字列検索
コンテスト
ユーザー ああ
提出日時 2026-06-04 20:46:15
言語 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
結果
WA  
実行時間 -
コード長 2,850 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,473 ms
コンパイル使用メモリ 174,792 KB
実行使用メモリ 10,676 KB
最終ジャッジ日時 2026-06-04 20:46:18
合計ジャッジ時間 2,254 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 WA * 10
権限があれば一括ダウンロードができます

ソースコード

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;
                rep(size, j) {
                    nodes[nxt].move[j] = nodes[0].nxt[j];
                }
                que.push_back(nxt);
            }
        }
        while (!que.empty()) {
            int u = que.front();
            que.pop_front();
            rep(size, 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++;
                    rep(size, j) {
                        nodes[nxt].move[j] = nodes[fail].move[j];
                    }
                    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