結果

問題 No.430 文字列検索
ユーザー KoshStormKoshStorm
提出日時 2018-09-25 16:15:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 26 ms / 2,000 ms
コード長 3,896 bytes
コンパイル時間 2,463 ms
コンパイル使用メモリ 178,796 KB
実行使用メモリ 25,856 KB
最終ジャッジ日時 2024-11-10 00:20:03
合計ジャッジ時間 2,319 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 26 ms
25,856 KB
testcase_02 AC 6 ms
9,088 KB
testcase_03 AC 6 ms
9,088 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 1 ms
6,816 KB
testcase_08 AC 3 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 18 ms
18,048 KB
testcase_12 AC 20 ms
20,604 KB
testcase_13 AC 19 ms
20,608 KB
testcase_14 AC 14 ms
16,128 KB
testcase_15 AC 10 ms
12,416 KB
testcase_16 AC 9 ms
12,288 KB
testcase_17 AC 9 ms
12,288 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i,n) for (long long i=0;i<(n);i++)
#define FOR(i,a,b) for (long long i=(a);i<(b);i++)
#define RREP(i,n) for(long long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl
#define dump(x)  cerr << #x << " => " << (x) << endl
#define dumpP(p) cerr << "( " << p.first << " , " << p.second << " )" << ends
#define SORT(c) sort((c).begin(),(c).end())
#define MIN(vec) *min_element(vec.begin(), vec.end())
#define MAX(vec) *max_element(vec.begin(), vec.end())
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end()) //ソートの必要あり
#define IN(n,m)  (!(m.find(n) == m.end()))
#define ENUM(m) for (auto itr = m.begin(); itr != m.end(); ++itr)
#define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> "  << itr->second << endl; }
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
#define ROUND(N) setprecision(N)
#define ROUND_PRINT(N,val) cout << fixed;cout << setprecision(N) << val << endl
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define INARR(h,w,x,y) (0 <= y && y < h && 0 <= x && x < w)
#define EQ(a,b) (abs(a - b) < 1e-10)
using namespace std;
//#define CHAR_MAX 127

struct Trie {
    bool leaf;
    int sz = 0;
    // node[0] is for failure link
    Trie* node[CHAR_MAX];
    vector<int> accept;
    Trie() {
        leaf = false;
        for(int i=0; i<CHAR_MAX; i++) node[i] = (Trie*)0;
    }
    void insert(const string &str){
        Trie *r = this;
        int dic_size = ++(r->sz);
        for(int i=0; i<str.length(); i++){
            char c = str[i];
            if(!r->node[c]) r->node[c] = new Trie;
            r = r->node[c];
        }
        r->accept.push_back(dic_size-1);
        r->leaf = true;
    }
};

class AhoCorasick {
private:
    Trie trie;
    void updateFailure() {
        Trie* root = &trie;
        queue<Trie*> que;
        for (int c = 1;c < CHAR_MAX;c++) {
            if (root->node[c]) {
                root->node[c]->node[0] = root;
                que.push(root->node[c]);
            }
            else root->node[c] = root;
        }
        while (!que.empty()) {
            Trie *t = que.front();que.pop();
            for (int c = 1;c < CHAR_MAX;c++) {
                if ( t->node[c]) {
                    que.push(t->node[c]);
                    Trie *r = t->node[0];
                    while (!r->node[c]) r = r->node[0];
                    t->node[c]->node[0] = r->node[c];
                    t->node[c]->accept.insert(t->node[c]->accept.end(), r->node[c]->accept.begin(), r->node[c]->accept.end());
                }
            }
        }
    }

public:
    AhoCorasick(const vector<string> &r) {
        for (int i = 0;i < r.size();i++) trie.insert(r[i]);
        updateFailure();
    }

    int match(string &target,vector<int> &result) {
        Trie* v = &trie;
        int count = 0;
        for (int i = 0;i < target.size();i++) {
            char c = target[i];
            while (! v->node[c]) {
                v = v->node[0];
            }
            v = v->node[c];
            for (int j = 0; j < v->accept.size(); ++j)
                result[v->accept[j]]++;
            count += (v->accept.size());
        }
        return count;
    }
};

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long M;
    string S;
    cin >> S >> M;
    vector<string> C(M);
    REP(i,M) cin >> C[i];
    
    AhoCorasick ac(C);
    vector<int> result(M);
    cout << ac.match(S,result) << endl;
    
}
0