結果
問題 | No.430 文字列検索 |
ユーザー | 👑 rin204 |
提出日時 | 2022-12-25 14:41:02 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 3,315 bytes |
コンパイル時間 | 3,028 ms |
コンパイル使用メモリ | 232,180 KB |
実行使用メモリ | 9,404 KB |
最終ジャッジ日時 | 2024-04-29 20:20:53 |
合計ジャッジ時間 | 4,291 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 30 ms
9,404 KB |
testcase_02 | AC | 10 ms
6,912 KB |
testcase_03 | AC | 9 ms
6,272 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 5 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 3 ms
5,376 KB |
testcase_11 | AC | 14 ms
6,608 KB |
testcase_12 | AC | 14 ms
6,976 KB |
testcase_13 | AC | 14 ms
6,972 KB |
testcase_14 | AC | 12 ms
6,364 KB |
testcase_15 | AC | 12 ms
6,304 KB |
testcase_16 | AC | 11 ms
7,192 KB |
testcase_17 | AC | 12 ms
7,320 KB |
ソースコード
#line 1 "A.cpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> using namespace std; using ll = long long; #define endl "\n" void print(){ cout << '\n'; } template <class Head, class... Tail> void print(Head &&head, Tail &&... tail) { cout << head; if (sizeof...(Tail)) cout << ' '; print(forward<Tail>(tail)...); } template<typename T> void print(vector<T> &A){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << '\n'; else cout << ' '; } } template<typename T, typename S> void prisep(vector<T> &A, S sep){ int n = A.size(); for(int i = 0; i < n; i++){ cout << A[i]; if(i == n - 1) cout << '\n'; else cout << sep; } } template<typename T> void print(vector<vector<T>> &A){ for(auto &row: A) print(row); } #line 3 "Library/C++/string/AhoCorasick.hpp" using namespace std; struct AhoCorasick{ vector<string> words; vector<map<char, int>> children; vector<vector<int>> match; vector<int> failure; AhoCorasick(){} void registe(string word){ words.push_back(word); } void build(){ children.assign(1, {}); match.assign(1, {}); for(int i = 0; i < words.size(); i++){ _register(i, words[i]); } failure.resize(children.size()); _create_failure(); } void _register(int i, string &word){ int k = 0; for(auto s:word){ if(children[k].count(s)) k = children[k][s]; else{ int le = children.size(); children[k][s] = le; children.push_back({}); match.push_back({}); k = le; } } match[k].push_back(i); } void _create_failure(){ queue<int> que; for(auto tmp:children[0]) que.push(tmp.second); while(!que.empty()){ int k = que.front(); int b = failure[k]; que.pop(); for(auto tmp:children[k]){ int j = tmp.second; failure[j] = _next(b, tmp.first); match[j].insert(match[j].end(), match[failure[j]].begin(), match[failure[j]].end()); que.push(j); } } } int _next(int k, char s){ while(1){ if(children[k].count(s)) return children[k][s]; else if(k == 0) return 0; k = failure[k]; } } vector<vector<int>> search(string text){ int k = 0; int le = text.size(); vector<vector<int>> matched(le, vector<int>()); for(int i = 0; i < le; i++){ k = _next(k, text[i]); for(auto m:match[k]){ matched[i - words[m].size() + 1].push_back(m); } } return matched; } }; #line 46 "A.cpp" void solve(){ string S; int n; cin >> S >> n; AhoCorasick ac; for(int i = 0; i < n; i++){ string T; cin >> T; ac.registe(T); } ac.build(); auto match = ac.search(S); int ls = S.size(); int ans = 0; for(int i = 0; i < match.size(); i++){ ans += match[i].size(); } print(ans); } int main(){ cin.tie(0)->sync_with_stdio(0); int t; t = 1; // cin >> t; while(t--) solve(); return 0; }