結果
問題 |
No.430 文字列検索
|
ユーザー |
![]() |
提出日時 | 2022-09-21 02:06:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 2,451 bytes |
コンパイル時間 | 1,819 ms |
コンパイル使用メモリ | 177,372 KB |
実行使用メモリ | 7,232 KB |
最終ジャッジ日時 | 2024-11-10 01:01:55 |
合計ジャッジ時間 | 2,180 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
/** * @FileName a.cpp * @Author kanpurin * @Created 2022.09.21 02:06:31 **/ #include "bits/stdc++.h" using namespace std; typedef long long ll; struct Trie { struct Node { array<int,26> ch; int cnt; int sub; Node () : cnt(0), sub(0) { fill(ch.begin(), ch.end(), -1); } }; vector<Node> nodes; Trie() : nodes(1) {} void insert(const string &s) { int t = 0; for (int i = 0; i < (int)s.size(); i++) { if (nodes[t].ch[s[i]-'A'] == -1) { nodes[t].ch[s[i]-'A'] = nodes.size(); nodes.push_back(Node()); } nodes[t].sub++; t = nodes[t].ch[s[i]-'A']; } nodes[t].sub++; nodes[t].cnt++; } }; struct AhoCorasick { Trie trie; vector<int> failure; vector<int> count; AhoCorasick() {} void insert(const string &s) { trie.insert(s); } void build() { for (int c = 0; c < 26; c++) { if (trie.nodes[0].ch[c] != -1) continue; trie.nodes[0].ch[c] = 0; } failure.resize(trie.nodes.size(),-1); count.resize(trie.nodes.size(),0); queue<int> que; que.push(0); while(!que.empty()) { int v = que.front(); que.pop(); for (int c = 0; c < 26; c++) { int to = trie.nodes[v].ch[c]; if (to <= 0) continue; count[to] = trie.nodes[to].cnt; que.push(to); int now = v; while(now != 0 && trie.nodes[failure[now]].ch[c] == -1) { now = failure[now]; } failure[to] = (now==0?0:trie.nodes[failure[now]].ch[c]); count[to] += count[failure[to]]; } } } int move(int idx, int c) { if (trie.nodes[idx].ch[c] == -1) { return move(failure[idx],c); } else { return trie.nodes[idx].ch[c]; } } }; int main() { string s;cin >> s; int n;cin >> n; AhoCorasick aho; for (int i = 0; i < n; i++) { string t;cin >> t; aho.insert(t); } aho.build(); int now = 0; int ans = 0; for (int i = 0; i < s.size(); i++) { now = aho.move(now,s[i]-'A'); ans += aho.count[now]; } cout << ans << endl; return 0; }