結果
問題 |
No.430 文字列検索
|
ユーザー |
![]() |
提出日時 | 2018-12-18 19:15:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 17 ms / 2,000 ms |
コード長 | 2,077 bytes |
コンパイル時間 | 2,755 ms |
コンパイル使用メモリ | 208,772 KB |
最終ジャッジ日時 | 2025-01-06 19:38:01 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int var = 26; int trans(char c) { return c - 'A'; } class aho_corasick { struct ac_node { int fail; vector<int> next; vector<int> ok; ac_node() : fail(-1), next(var, -1) {} }; vector<int> unite(const vector<int>& a, const vector<int>& b) { vector<int> res; set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res)); return move(res); } int n; vector<ac_node> dat; public: aho_corasick(const vector<string>& Ts) : n(Ts.size()), dat(1) { int now; dat[0].fail = 0; for (int i = 0; i < n; i++) { auto &T = Ts[i]; now = 0; for (auto c : T) { if (dat[now].next[trans(c)] == -1) { dat[now].next[trans(c)] = dat.size(); dat.emplace_back(); } now = dat[now].next[trans(c)]; } dat[now].ok.push_back(i); } queue<int> q; for (int i = 0; i < var; i++) { if (dat[0].next[i] == -1) { dat[0].next[i] = 0; } else { dat[dat[0].next[i]].fail = 0; q.push(dat[0].next[i]); } } while (!q.empty()) { now = q.front(); q.pop(); for (int i = 0; i < var; i++) { if (dat[now].next[i] != -1) { int nx = dat[now].fail; while (dat[nx].next[i] == -1) { nx = dat[nx].fail; } int nex = dat[now].next[i]; dat[nex].fail = dat[nx].next[i]; dat[nex].ok = unite(dat[nex].ok, dat[dat[nx].next[i]].ok); q.push(nex); } } } } const vector<int>& ok(int i) const { return dat[i].ok; } int size() const { return dat.size(); } int get_next(int id, char c) const { while (dat[id].next[trans(c)] == -1) id = dat[id].fail; return dat[id].next[trans(c)]; } vector<int> count(const string& S) const { vector<int> res(n); int now = 0; for (auto c : S) { now = get_next(now, c); for (auto k : dat[now].ok) res[k]++; } return res; } }; int main() { string S; int M; cin >> S >> M; vector<string> C(M); for (int i = 0; i < M; i++) { cin >> C[i]; } aho_corasick ac(C); auto cnt = ac.count(S); cout << accumulate(cnt.begin(), cnt.end(), 0LL) << endl; return 0; }