結果
問題 | No.430 文字列検索 |
ユーザー | yuri3 |
提出日時 | 2022-10-12 23:31:53 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 10 ms / 2,000 ms |
コード長 | 2,416 bytes |
コンパイル時間 | 2,577 ms |
コンパイル使用メモリ | 213,160 KB |
実行使用メモリ | 7,048 KB |
最終ジャッジ日時 | 2023-09-08 18:42:36 |
合計ジャッジ時間 | 3,630 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 10 ms
7,048 KB |
testcase_02 | AC | 4 ms
4,380 KB |
testcase_03 | AC | 3 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,384 KB |
testcase_07 | AC | 1 ms
4,384 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 8 ms
5,324 KB |
testcase_12 | AC | 9 ms
5,584 KB |
testcase_13 | AC | 9 ms
5,732 KB |
testcase_14 | AC | 8 ms
5,196 KB |
testcase_15 | AC | 6 ms
5,140 KB |
testcase_16 | AC | 6 ms
5,352 KB |
testcase_17 | AC | 6 ms
5,372 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using i64 = long long; using VI = vector<int>; using pii = pair<int, int>; template <class Node> struct trie { vector<Node> tr; trie() { tr.push_back(Node()); }; int add(const string &s) { int n = s.size(); int p = 0; for (int i = 0; i < n; i++) { int c = s[i] - 'A'; if (!tr[p][c]) { tr[p][c] = tr.size(); tr.emplace_back(tr[p][c], tr[p].dep + 1); } p = tr[p][c]; } return p; } int size() const { return tr.size(); } }; template <class Node> struct ACAutomaton : public trie<Node> { vector<int> fail; ACAutomaton() { this->tr.push_back(Node()); }; void BuildAC() { fail.resize(this->tr.size()); queue<int> Q; for (int i = 0; i < 26; i++) if (this->tr[0][i]) Q.push(this->tr[0][i]); while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int i = 0; i < 26; i++) { if (this->tr[u][i]) fail[this->tr[u][i]] = this->tr[fail[u]][i], Q.push(this->tr[u][i]); else this->tr[u][i] = this->tr[fail[u]][i]; } } return; } }; struct TrieNode { TrieNode() { id = 0, dep = 0, nxt = array<int, 26>(); }; TrieNode(int _id, int _dep) : id(_id), dep(_dep) {} int id; int dep; array<int, 26> nxt = {}; int &operator[](const int x) { return this->nxt[x]; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; int m; cin >> s >> m; ACAutomaton<TrieNode> ac; vector<int> pos(m + 1); for (int i = 1; i <= m; i++) { string res; cin >> res; pos[i] = ac.add(res); } ac.BuildAC(); vector<int> val(ac.size()); vector<vector<int>> adj(ac.size()); for (int i = 0; i < ac.size(); i++) { if (i != ac.fail[i]) adj[ac.fail[i]].push_back(i); } int p = 0; for (auto it : s) { p = ac.tr[p][it - 'A']; val[p]++; } function<void(int)> dfs = [&](int u) { for (auto v : adj[u]) { dfs(v); val[u] += val[v]; } }; dfs(0); int ans = 0; for (int i = 1; i <= m; i++) ans += val[pos[i]]; cout << ans << endl; return 0; }