結果
問題 | No.430 文字列検索 |
ユーザー | y |
提出日時 | 2021-05-25 19:43:01 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 5,818 bytes |
コンパイル時間 | 1,868 ms |
コンパイル使用メモリ | 193,428 KB |
実行使用メモリ | 16,360 KB |
最終ジャッジ日時 | 2024-11-10 00:56:47 |
合計ジャッジ時間 | 2,554 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 25 ms
16,360 KB |
testcase_02 | AC | 10 ms
8,520 KB |
testcase_03 | AC | 8 ms
6,980 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 1 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 | 13 ms
8,468 KB |
testcase_12 | AC | 14 ms
8,820 KB |
testcase_13 | AC | 14 ms
8,820 KB |
testcase_14 | AC | 11 ms
7,628 KB |
testcase_15 | AC | 10 ms
7,764 KB |
testcase_16 | AC | 12 ms
9,428 KB |
testcase_17 | AC | 11 ms
9,304 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; // #define LOCAL // 提出時はコメントアウト #define DEBUG_ typedef long long ll; const double EPS = 1e-9; const ll INF = ((1LL<<62)-(1LL<<31)); typedef vector<ll> vecl; typedef pair<ll, ll> pairl; template<typename T> using uset = unordered_set<T>; template<typename T, typename U> using mapv = map<T,vector<U>>; template<typename T, typename U> using umap = unordered_map<T,U>; #define ALL(v) v.begin(), v.end() #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i, n) REP(i, 0, n) #define sz(x) (ll)x.size() ll llceil(ll a,ll b) { return (a+b-1)/b; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> vector<vector<T>> genarr(ll n, ll m, T init) { return vector<vector<T>>(n,vector<T>(m,init)); } ///// DEBUG #define DUMPOUT cerr #define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++) template<typename T>istream&operator>>(istream&is,vector<T>&vec){for(T&x:vec)is>>x;return is;} template<typename T,typename U>ostream&operator<<(ostream&os,pair<T,U>&pair_var){os<<"("<<pair_var.first<<", "<<pair_var.second<<")";return os;} template<typename T>ostream&operator<<(ostream&os,const vector<T>&vec){os<<"{";for(int i=0;i<vec.size();i++){os<<vec[i]<<(i+1==vec.size()?"":", ");} os<<"}";return os;} template<typename T,typename U>ostream&operator<<(ostream&os,map<T,U>&map_var){os<<"{";repi(itr,map_var){os<<*itr;itr++;if(itr!=map_var.end())os<<", ";itr--;} os<<"}";return os;} template<typename T>ostream&operator<<(ostream&os,set<T>&set_var){os<<"{";repi(itr,set_var){os<<*itr;itr++;if(itr!=set_var.end())os<<", ";itr--;} os<<"}";return os;} void dump_func(){DUMPOUT<<endl;} template<class Head,class...Tail>void dump_func(Head&&head,Tail&&...tail){DUMPOUT<<head;if(sizeof...(Tail)>0){DUMPOUT<<", ";} dump_func(std::move(tail)...);} #ifndef LOCAL #undef DEBUG_ #endif #ifdef DEBUG_ #define DEB #define dump(...) \ DUMPOUT << " " << string(#__VA_ARGS__) << ": " \ << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" \ << endl \ << " ", \ dump_func(__VA_ARGS__) #else #define DEB if (false) #define dump(...) #endif ////////// #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using MatchedPair = vector<pair<string,pairl>>; struct AhoCorasick { char e; vector<string> Ps; vector<vecl> V; // V[i]: 状態iと対応するパターン群 (iに到達=パターンiが検出) vecl failure; // failure[i]: 検索失敗時の状態iの遷移先 vector<vecl> g; // g[i][c]: 状態iから遷移c+'a'(c+e)した時の遷移先 AhoCorasick(vector<string> patterns, char e = 'a') : Ps(patterns), e(e) { // edgeに文字, nodeに状態 build(); // Trie木を作成 make_failure(); // BFSでfailureを埋めていく } void build() { g.emplace_back(vecl(26,0)); // g[0][i] = 0 V.emplace_back(vecl()); rep(i,sz(Ps)) { ll v = 0; for (auto _c : Ps[i]) { int c = _c - e; if (v > 0 && g[v][c] != -1) { v = g[v][c]; continue; } else if (v == 0 && g[v][c] != 0) { v = g[v][c]; continue; } int vs = sz(V); V.emplace_back(vecl()); g.emplace_back(vecl(26,-1)); g[v][c] = vs; v = vs; } assert(v < sz(V)); V[v].emplace_back(i); } } void make_failure() { failure.assign(sz(V)+1,0LL); queue<ll> S; S.push(0); while (!S.empty()) { ll current = S.front(); S.pop(); rep(i,26) { ll next = g[current][i]; if (next <= 0) continue; S.push(next); if (current != 0) { // 最長の接尾辞をfailureに ll f = failure[current]; while (g[f][i] == -1) f = failure[f]; failure[next] = g[f][i]; // fからi+'a'の遷移ができる状態fを探して,その遷移先g[f][i]をnextのfailureとする for (auto p : V[failure[next]]) V[next].emplace_back(p); } } } } void search(const string &S, MatchedPair &X) { // マッチしたものはXに格納 ll v = 0; rep(i,sz(S)) { int c = S[i] - e; while (g[v][c] == -1) v = failure[v]; v = g[v][c]; rep(j,sz(V[v])) { string x = Ps[V[v][j]]; X.emplace_back(x,pairl{i-sz(x)+1,i}); } } } void print() { rep(i,sz(V)) { rep(j,26) { int p = i == 0 ? 0 : -1; if (g[i][j] == p) continue; printf("%d -> %d (%c)\n",i,g[i][j],j+e); } } dump(failure); } }; int solve(ostringstream &cout) { #ifdef LOCAL ifstream in("../../Atcoder/input.txt"); cin.rdbuf(in.rdbuf()); #endif string S; cin>>S; ll M; cin>>M; vector<string> Ps(M); rep(q,M) cin>>Ps[q]; MatchedPair res; AhoCorasick ac(Ps,'A'); ac.search(S,res); cout << sz(res) << endl; return 0; } int main() { ostringstream oss; int res = solve(oss); cout << oss.str(); return res; }