結果
問題 | No.430 文字列検索 |
ユーザー | eto_nagisa |
提出日時 | 2019-11-02 12:48:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 17 ms / 2,000 ms |
コード長 | 3,452 bytes |
コンパイル時間 | 2,190 ms |
コンパイル使用メモリ | 215,020 KB |
実行使用メモリ | 8,100 KB |
最終ジャッジ日時 | 2024-11-10 00:36:22 |
合計ジャッジ時間 | 2,686 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 17 ms
8,100 KB |
testcase_02 | AC | 7 ms
5,248 KB |
testcase_03 | AC | 6 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 3 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 12 ms
6,064 KB |
testcase_12 | AC | 13 ms
6,440 KB |
testcase_13 | AC | 12 ms
6,564 KB |
testcase_14 | AC | 10 ms
5,700 KB |
testcase_15 | AC | 8 ms
5,376 KB |
testcase_16 | AC | 8 ms
5,508 KB |
testcase_17 | AC | 8 ms
5,508 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; using ll = long long; #define REP(i, n) for (int i = 0; i < n; ++i) #define ALL(v) v.begin(), v.end() using namespace std; // 入力文字列に対してマッチするパターンを検索 // O(N + M) // N := 入力文字列, M := パターン文字列の長さ合計 /* 1. パターンから Trie 木を作成. 2. 各ノードが表す文字列の末尾と一致するノードの内, 文字列長が最大のノードへ辺を張る. そのようなノードが存在しなければ根に辺を張る. この処理は bfs で可能. 各ノードはその祖先が一致する文字列の情報も持つ. 3. PMA(パターンマッチングオートマトン)の完成! */ // 出現文字 struct characters { // lower alphabets static int const size = 26; static int convert(char c) { return c - 'A'; } static char invert(int i) { return i + 'A'; } }; template <typename Char> struct AhoCorasick { static constexpr int invalid = -1; struct PMA { int fail; vector<int> next, accept; PMA() : fail(invalid), next(Char::size, invalid) {} }; const int K; vector<PMA> nodes; int next(int index, char cc) { int c = Char::convert(cc); int now = index; while (nodes[now].next[c] == invalid && now != 0) { now = nodes[now].fail; } now = nodes[now].next[c]; if (now == invalid) now = 0; return now; } AhoCorasick(const vector<string> &ts) : K((int)ts.size()) { const int root = 0; // root node nodes.emplace_back(); nodes[root].fail = root; for (int i = 0; i < K; i++) { int now = root; for (auto cs : ts[i]) { int c = Char::convert(cs); if (nodes[now].next[c] == invalid) { nodes[now].next[c] = (int)nodes.size(); nodes.emplace_back(); } now = nodes[now].next[c]; } nodes[now].accept.push_back(i); } queue<int> que; for (int c = 0; c < Char::size; c++) { if (nodes[root].next[c] != invalid) { nodes[nodes[root].next[c]].fail = root; que.push(nodes[root].next[c]); } } while (!que.empty()) { int now = que.front(); que.pop(); for (int c = 0; c < Char::size; c++) { if (nodes[now].next[c] != invalid) { que.push(nodes[now].next[c]); int nxt = next(nodes[now].fail, Char::invert(c)); nodes[nodes[now].next[c]].fail = nxt; for (auto ac : nodes[nxt].accept) { nodes[nodes[now].next[c]].accept.push_back(ac); } } } } // 最悪O(1)にする部分 for (int c = 0; c < Char::size; c++) { if (nodes[root].next[c] != invalid) { que.push(nodes[root].next[c]); } else { nodes[root].next[c] = root; } } while (!que.empty()) { int p = que.front(); que.pop(); for (int c = 0; c < Char::size; c++) { if (nodes[p].next[c] == invalid) { int nxt = nodes[nodes[p].fail].next[c]; assert(nxt != invalid); nodes[p].next[c] = nxt; } else { que.push(nodes[p].next[c]); } } } // ここまで } vector<vector<int>> match(const string &str) { vector<vector<int>> ret(K); int now = 0; for (int i = 0; i < (int)str.size(); i++) { now = next(now, str[i]); for (auto k : nodes[now].accept) { ret[k].push_back(i); } } return ret; } }; int main() { string s; cin >> s; int m; cin >> m; vector<string> v(m); REP(i, m) cin >> v[i]; AhoCorasick<characters> aho(v); ll ans = 0; auto res = aho.match(s); for (auto a : res) ans += a.size(); cout << ans << endl; }