結果

問題 No.430 文字列検索
ユーザー IKyoproIKyopro
提出日時 2020-10-29 16:02:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 4,719 bytes
コンパイル時間 2,745 ms
コンパイル使用メモリ 222,184 KB
実行使用メモリ 8,132 KB
最終ジャッジ日時 2024-11-10 00:48:29
合計ジャッジ時間 2,861 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;
template<class T> bool chmin(T& a,T b){if(a>b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b){if(a<b) {a = b; return true;} return false;}
#define all(x) (x).begin(),(x).end()
#define debug(x)  cerr << #x << " = " << (x) << endl;


template<int char_size,int margin>
class Trie{
private:
    struct Node{
        int ne[char_size];
        int num;
        int subtree_num;
        vec<int> accept;
        Node():num(0){
            memset(ne,-1,sizeof(ne));
        }
    };

    int root;
public:
    vec<Node> nodes;
    Trie():root(0){
        nodes.push_back(Node());
    }

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

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

    void add(const string& S,int s_id,int node_id,int id){
        if(s_id==S.size()) update_direct(node_id,id);
        else{
            int c = S[s_id]-margin;
            if(nodes[node_id].ne[c]==-1){
                nodes[node_id].ne[c] = (int) nodes.size();
                nodes.push_back(Node());
            }
            add(S,s_id+1,nodes[node_id].ne[c],id);
            update_child(node_id,nodes[node_id].ne[c]);
        }
    }

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

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

    template<class F>
    void query(const string& S,F& f,int s_id,int node_id){
        for(auto& id:nodes[node_id].accept) f(id);
        if(s_id==S.size()) return ;
        else{
            int c = S[s_id]-margin;
            if(nodes[node_id].ne[c]==-1) return ;
            query(S,f,s_id+1,nodes[node_id].ne[c]);
        }
    }

    template<class F>
    void query(const string& S,F& f){
        query(S,f,0,0);
    }

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

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

};

template<int char_size,int margin>
struct AhoCorasick:Trie<char_size+1,margin>{
    using Trie<char_size+1,margin>::Trie;
    const int FAIL = char_size;
    vec<int> cnt;

    void build(bool heavy=true){
        int n = this->size();
        cnt.resize(n);
        for(int i=0;i<n;i++){
            cnt[i] = (int) this->nodes[i].accept.size();
        }
        queue<int> Q;
        for(int i=0;i<=char_size;i++){
            if(~this->nodes[0].ne[i]){
                this->nodes[this->nodes[0].ne[i]].ne[FAIL] = 0;
                Q.push(this->nodes[0].ne[i]);
            }else{
                this->nodes[0].ne[i] = 0;
            }
        }
        while(!Q.empty()){
            auto &now = this->nodes[Q.front()];
            cnt[Q.front()] += cnt[now.ne[FAIL]];
            Q.pop();
            int f = now.ne[FAIL];
            for(int i=0;i<char_size;i++){
                if(~now.ne[i]){
                    this->nodes[now.ne[i]].ne[FAIL] = this->nodes[f].ne[i];
                    if(heavy){
                        auto &u = this->nodes[now.ne[i]].accept;
                        auto &v = this->nodes[this->nodes[f].ne[i]].accept;
                        vec<int> acc;
                        set_union(all(u),all(v),back_insert_iterator(acc));
                        u = acc;
                    }
                    Q.push(now.ne[i]);
                }else{
                    now.ne[i] = this->nodes[f].ne[i];
                }
            }
        }
    }
    map<int,int> match(string &S,int now=0){
        map<int,int> res;
        for(auto& c:S){
            while(this->nodes[now].ne[c-margin]==-1){
                now = this->nodes[now].ne[FAIL];
            }
            now = this->nodes[now].ne[c-margin];
            for(auto& v:this->nodes[now].accept) res[v]++;
        }
        return res;
    }
    pair<ll, int > move(const char &c, int now = 0) {
        now = this->nodes[now].ne[c - margin];
        return {cnt[now], now};
    }

    pair<ll, int > move(const string &str, int now = 0) {
        ll sum = 0;
        for(auto &c : str) {
            auto ne = move(c, now);
            sum += ne.first;
            now = ne.second;
        }
        return {sum, now};
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int M;
    cin >> M;
    AhoCorasick<26,'A'> ushi;
    for(int i=0;i<M;i++){
        string s;
        cin >> s;
        ushi.add(s);
    }
    ushi.build();
    auto res = ushi.match(S);
    ll ans = 0;
    for(auto& x:res){
        ans += x.second;
    }
    cout << ushi.move(S).first << "\n";
}
0