結果
問題 | No.430 文字列検索 |
ユーザー | yuri3 |
提出日時 | 2022-10-12 23:31:53 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 2,416 bytes |
コンパイル時間 | 2,152 ms |
コンパイル使用メモリ | 214,020 KB |
実行使用メモリ | 6,996 KB |
最終ジャッジ日時 | 2024-11-10 01:02:02 |
合計ジャッジ時間 | 2,644 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 9 ms
6,996 KB |
testcase_02 | AC | 3 ms
5,248 KB |
testcase_03 | AC | 3 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 7 ms
5,588 KB |
testcase_12 | AC | 7 ms
5,972 KB |
testcase_13 | AC | 8 ms
5,844 KB |
testcase_14 | AC | 5 ms
5,264 KB |
testcase_15 | AC | 5 ms
5,248 KB |
testcase_16 | AC | 5 ms
5,264 KB |
testcase_17 | AC | 5 ms
5,272 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; }