結果
問題 | No.430 文字列検索 |
ユーザー | pockyny |
提出日時 | 2022-09-11 00:04:47 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 6,192 bytes |
コンパイル時間 | 1,253 ms |
コンパイル使用メモリ | 99,556 KB |
実行使用メモリ | 11,764 KB |
最終ジャッジ日時 | 2024-11-10 01:01:34 |
合計ジャッジ時間 | 1,936 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 13 ms
9,088 KB |
testcase_02 | AC | 9 ms
11,764 KB |
testcase_03 | AC | 9 ms
11,484 KB |
testcase_04 | AC | 1 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 | 4 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 1 ms
5,248 KB |
testcase_11 | AC | 15 ms
11,264 KB |
testcase_12 | AC | 15 ms
11,520 KB |
testcase_13 | AC | 13 ms
11,544 KB |
testcase_14 | AC | 12 ms
11,520 KB |
testcase_15 | AC | 11 ms
11,520 KB |
testcase_16 | AC | 11 ms
11,648 KB |
testcase_17 | AC | 10 ms
11,648 KB |
ソースコード
#include <iostream> #include <vector> #include <string> #include <array> #include <queue> using namespace std; const int alpha = 26;//alphabet_size struct AhoCorasick{ int sumLength = 0;//sum of |P_i| + 1 vector<string> pattern; vector<array<int,alpha>> Trie; vector<int> failureLink; vector<int> isEnd; vector<int> trulyFailureLink,dist; // it is not used for counting but used for enumerating vector<vector<int>> failureTree; // it is not used for enumerating but used for counting AhoCorasick(vector<string> &P){ createTrie(P); createFailureLink(); createTrulyFailureLink(); createFailureTree(); } //make Trie void createTrie(vector<string> &P){ pattern = P; sumLength = 1; for(string str:pattern) sumLength += str.size(); Trie.resize(sumLength + 1); isEnd.resize(sumLength + 1); int index = 1; int maxPosition = 1; for(string str:pattern){ int position = 1; //the index of root = 1; int latestEnd = 1; for(char chr:str){ if(!Trie[position][chr - 'A']) Trie[position][chr - 'A'] = ++maxPosition; position = Trie[position][chr - 'A']; } isEnd[position] = index++; } } //make failureLink void createFailureLink(){ failureLink.resize(sumLength + 1); dist.resize(sumLength + 1); failureLink[1] = 1; queue<pair<int,int>> bfsQue; bfsQue.push({1,0}); while(bfsQue.size()){ int position = bfsQue.front().first; dist[position] = bfsQue.front().second; bfsQue.pop(); for(int i=0;i<alpha;i++){ if(Trie[position][i]){ int nextPosition = Trie[position][i]; bfsQue.push({nextPosition,dist[position] + 1}); int tmp = position; while(tmp!=1 && !Trie[failureLink[tmp]][i]){ tmp = failureLink[tmp]; } if(Trie[failureLink[tmp]][i] && nextPosition!=Trie[failureLink[tmp]][i]){ failureLink[nextPosition] = Trie[failureLink[tmp]][i]; }else{ failureLink[nextPosition] = 1; } } } } } // make trulyFailureLink void createTrulyFailureLink(){ trulyFailureLink.resize(sumLength + 1); queue<int> bfsQue; bfsQue.push(1); while(bfsQue.size()){ int position = bfsQue.front(); bfsQue.pop(); if(position!=1){ if(isEnd[failureLink[position]]) trulyFailureLink[position] = failureLink[position]; else trulyFailureLink[position] = trulyFailureLink[failureLink[position]]; }else{ trulyFailureLink[position] = 1; } for(int i=0;i<alpha;i++){ if(Trie[position][i]){ bfsQue.push(Trie[position][i]); } } } } // make failureTree void createFailureTree(){ failureTree.resize(sumLength + 1); for(int i=2;i<=sumLength;i++){ failureTree[failureLink[i]].push_back(i); } } // sでpatternが存在する位置を列挙する vector<vector<int>> enumerate(string S){ S.push_back('z' + 1); vector<vector<int>> enume(pattern.size()); int position = 1; int left = 0; for(char chr:S){ while(position!=1 && !(chr - 'A'<alpha && Trie[position][chr - 'A'])){ left += dist[position] - dist[failureLink[position]]; position = failureLink[position]; } if(chr - 'A'<alpha && Trie[position][chr - 'A']) position = Trie[position][chr - 'A']; else left++; int tmp = position; int tmpLeft = left; while(tmp!=1){ if(isEnd[tmp]) enume[isEnd[tmp] - 1].push_back(tmpLeft); tmpLeft += dist[tmp] - dist[trulyFailureLink[tmp]]; tmp = trulyFailureLink[tmp]; } } return enume; } //count用のdfs関数 vector<int> cnt; void dfs_cnt(int pos){ if(pos==0) exit(1); for(int nextPos:failureTree[pos]){ dfs_cnt(nextPos); cnt[pos] += cnt[nextPos]; } } // sにいくつpatternが存在するか数える vector<int> countPattern(string S){ cnt.resize(sumLength + 1); S.push_back('z' + 1); //記事中の7の代用 int position = 1; for(char chr:S){ while(position!=1 && !(chr - 'A'<alpha && Trie[position][chr - 'A'])){ position = failureLink[position]; } if(chr - 'A'<alpha && Trie[position][chr - 'A']) position = Trie[position][chr - 'A']; if(position!=1) cnt[position]++; } dfs_cnt(1); vector<int> resultOfCount(pattern.size()); for(int i=1;i<=sumLength;i++){ if(isEnd[i]){ resultOfCount[isEnd[i] - 1] = cnt[i];// 1引くことに注意 } } return resultOfCount; } void debugAhoCora(){ for(int i=0;i<Trie.size();i++){ cout << "i = " << i << ": "; for(int j=0;j<alpha;j++){ if(Trie[i][j]) cout << "{" << char('a' + j) << ":" << Trie[i][j] << "} "; } cout << "failure = " << failureLink[i] << endl; } cout << "isEnd = "; for(int i=0;i<Trie.size();i++) cout << isEnd[i] << " "; cout << endl; cout << "trulyFailureLink = "; for(int i=0;i<Trie.size();i++) cout << trulyFailureLink[i] << " "; cout << endl; } }; int main(){ string s; cin >> s; int i,m; cin >> m; vector<string> t(m); for(i=0;i<m;i++) cin >> t[i]; AhoCorasick aho(t); int ans = 0; vector<vector<int>> enu = aho.enumerate(s); vector<int> cnt = aho.countPattern(s); for(i=0;i<m;i++) ans += cnt[i]; cout << ans << endl; }