結果
問題 | No.430 文字列検索 |
ユーザー | KoshStorm |
提出日時 | 2018-09-25 17:38:40 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 47 ms / 2,000 ms |
コード長 | 2,649 bytes |
コンパイル時間 | 2,287 ms |
コンパイル使用メモリ | 174,432 KB |
実行使用メモリ | 26,112 KB |
最終ジャッジ日時 | 2024-04-15 09:50:17 |
合計ジャッジ時間 | 3,329 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 47 ms
26,112 KB |
testcase_02 | AC | 10 ms
9,216 KB |
testcase_03 | AC | 9 ms
9,472 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 3 ms
6,944 KB |
testcase_09 | AC | 3 ms
6,940 KB |
testcase_10 | AC | 3 ms
6,944 KB |
testcase_11 | AC | 27 ms
18,412 KB |
testcase_12 | AC | 33 ms
20,848 KB |
testcase_13 | AC | 38 ms
20,992 KB |
testcase_14 | AC | 23 ms
16,512 KB |
testcase_15 | AC | 17 ms
12,544 KB |
testcase_16 | AC | 14 ms
12,544 KB |
testcase_17 | AC | 14 ms
12,544 KB |
ソースコード
#include <bits/stdc++.h> #define REP(i,n) for (long long i=0;i<(n);i++) using namespace std; typedef int string_size; struct Trie { int sz = 0; Trie* node[CHAR_MAX]; Trie* failure; vector<string_size> accept; Trie() { for(string_size i=0; i<CHAR_MAX; i++) node[i] = (Trie*)0;} void insert(const string &str){ Trie *r = this; int dic_size = ++(r->sz); for(string_size 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); } }; // パターンマッチ, 辞書 <- 文字列(全ての部分列に分解) class AhoCorasick { private: Trie trie; void updateFailure() { Trie* root = ≜ queue<Trie*> que; for (char c = 0;c < CHAR_MAX;c++) { if (root->node[c]) { root->node[c]->failure = root; que.push(root->node[c]); } else root->node[c] = root; } while (!que.empty()) { Trie *t = que.front();que.pop(); for (char c = 0;c < CHAR_MAX;c++) { if ( t->node[c]) { que.push(t->node[c]); Trie *r = t->failure; while (!r->node[c]) r = r->failure; t->node[c]->failure = 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> &pattern) { for (int i = 0;i < pattern.size();i++) trie.insert(pattern[i]); updateFailure(); } // targetの部分列のうち,patternと一致するところをマッチング. // result[idx] := (辞書内の)idx番目の単語とマッチングする回数. // target := 一致させる単語 int match(string &target,vector<string_size> &result) { Trie* v = ≜ int count = 0; for (string_size i = 0;i < target.size();i++) { char c = target[i]; while (! v->node[c]) v = v->failure; v = v->node[c]; for (string_size 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; }