結果

問題 No.430 文字列検索
ユーザー yebityonyebityon
提出日時 2017-11-27 19:37:34
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 3,993 bytes
コンパイル時間 2,011 ms
コンパイル使用メモリ 182,868 KB
実行使用メモリ 8,748 KB
最終ジャッジ日時 2024-11-10 00:18:33
合計ジャッジ時間 2,355 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
using ll = long long;
using ld =long double;
//#define int ll
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,pii> piii;
#define mp make_pair
#define MAX 26
#define OFFSET 'A'
struct Node{
    int nxt[MAX+1]; // 次のalphabeteのノード番号
    int exist; // 子ども以下に存在する文字列の数の合計
    vi accept; // その文字列id
    Node() : exist(0){memset(nxt, -1, sizeof(nxt));}
};
struct Trie{
    vector<Node>nodes;
    int root;
    Trie() : root(0){nodes.push_back(Node());}
    
    void update_direct(int node,int id){
        nodes[node].accept.push_back(id);
    }
    void update_child(int node,int child,int id){
        ++nodes[node].exist;
    }
    void add(const string &str,int str_index,int node_index,int id){
        if(str_index == str.size())
            update_direct(node_index, id);
        else{
            const int c = str[str_index] - OFFSET;
            if(nodes[node_index].nxt[c] == -1) {
                nodes[node_index].nxt[c] = (int) nodes.size();
                nodes.push_back(Node());
            }
            add(str, str_index + 1, nodes[node_index].nxt[c], id);
            update_child(node_index, nodes[node_index].nxt[c], id);
        }
    }
    void add(const string &str,int id){add(str, 0, 0, id);}
    void add(const string &str){add(str, nodes[0].exist);}
    int size(){return (nodes[0].exist);}
    int nodesize(){return ((int) nodes.size());}
};
struct Aho_Corasick : Trie{
    static const int FAIL = MAX;
    vi correct;
    Aho_Corasick() : Trie() {}
    
    void build(){
        correct.resize(nodes.size());
        rep(i,nodes.size())correct[i]=(int)nodes[i].accept.size();
        
        queue<int> que;
        rep(i,MAX+1){
            if(~nodes[0].nxt[i]) {
                nodes[nodes[0].nxt[i]].nxt[FAIL] = 0;
                que.emplace(nodes[0].nxt[i]);
            }else nodes[0].nxt[i] = 0;
        }
        while(!que.empty()) {
            Node &now = nodes[que.front()];
            correct[que.front()] += correct[now.nxt[FAIL]];
            que.pop();
            rep(i,MAX){
                if(now.nxt[i] == -1) continue;
                int fail = now.nxt[FAIL];
                while(nodes[fail].nxt[i] == -1) {
                    fail = nodes[fail].nxt[FAIL];
                }
                nodes[now.nxt[i]].nxt[FAIL] = nodes[fail].nxt[i];
                
                auto &u = nodes[now.nxt[i]].accept;
                auto &v = nodes[nodes[fail].nxt[i]].accept;
                vi accept;
                set_union(all(u),all(v),back_inserter(accept));
                u=accept;
                que.emplace(now.nxt[i]);
            }
        }
    }
    int match(const string &str,vi &result,int now=0){
        result.assign(size(),0);
        int count=0;
        for(auto &c:str) {
            while(nodes[now].nxt[c-OFFSET]==-1)now=nodes[now].nxt[FAIL];
            now = nodes[now].nxt[c-OFFSET];
            count += correct[now];
            for(auto &v:nodes[now].accept)result[v]++;
        }
        return count;
    }
    int next(int now,char c){
        while(nodes[now].nxt[c-OFFSET]==-1)now=nodes[now].nxt[FAIL];
        return nodes[now].nxt[c-OFFSET];
    }
};

signed main(){
    string s;
    cin >>s;
    Aho_Corasick Ahc;
    int n; cin>>n;
    rep(i,n){
        string temp; cin>>temp;
        Ahc.add(temp);
    }
    Ahc.build();
    vector<int>d;
    cout<<Ahc.match(s,d)<<endl;
    //cout<<"yes"<<endl;
}
0