結果
問題 | No.430 文字列検索 |
ユーザー | HIcoder |
提出日時 | 2024-02-09 17:50:00 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 4,004 bytes |
コンパイル時間 | 1,854 ms |
コンパイル使用メモリ | 147,452 KB |
実行使用メモリ | 10,324 KB |
最終ジャッジ日時 | 2024-11-10 01:10:05 |
合計ジャッジ時間 | 2,317 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 39 ms
10,324 KB |
testcase_02 | AC | 11 ms
6,820 KB |
testcase_03 | AC | 10 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,816 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 6 ms
6,820 KB |
testcase_09 | AC | 2 ms
6,816 KB |
testcase_10 | AC | 3 ms
6,816 KB |
testcase_11 | AC | 22 ms
7,248 KB |
testcase_12 | AC | 23 ms
7,736 KB |
testcase_13 | AC | 22 ms
7,608 KB |
testcase_14 | AC | 19 ms
6,816 KB |
testcase_15 | AC | 18 ms
6,820 KB |
testcase_16 | AC | 15 ms
6,820 KB |
testcase_17 | AC | 14 ms
6,816 KB |
ソースコード
#include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<numeric> #include<queue> #include<cmath> #include<cassert> #include<unordered_map> #include<optional> #include<tuple> using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef std::pair<int,int> P; typedef std::pair<int,P> PP; const ll MOD=998244353; map<string,int> stringid; vector<int> ans; struct Aho_Corasick{ typedef std::unordered_map<char,int> MP; std::vector<MP> trie; std::vector<int> cnt;//cnt,treeの大きさは同じ const int root=0; Aho_Corasick(){ trie.push_back(MP()); cnt.push_back(0); } std::unordered_map<int,std::vector<std::string>> output; void add(const std::vector<std::string>& terms){ for(const std::string& term:terms){ add(term); } } //計算量は挿入する文字列の長さの和 int add(const std::string& string){ int now=root;//根 for(char c:string){ if(trie[now].count(c)){ now=trie[now][c]; }else{ int pre=now; now=trie.size(); cnt.push_back(0); trie.push_back(MP()); trie[pre][c]=now; } } cnt[now]++;//終端文字列 output[now].push_back(string);//終端ノードに対してsを入れる return now; } void match(const std::string& string){ //std::cout<<"target: string="<<string<<std::endl; int now=root; for(int i=0;i<string.size();i++){ char c=string[i]; //今の状態nowからcを用いて遷移する場所を探す. while(!go(now,c)){ now=failure[now]; } //go(now,string[i]).firstがtrue now=*go(now,c); for(const auto& x:output[now]){ //ノードnowで終わる場合 ans[stringid[x]]++; //std::cout<<"start="<<i-x.size()+1<<",goal="<<i<<",string:"<<x<<std::endl; } } } std::vector<int> failure; std::vector<int> dist; //ノードnowから文字列cをうけていく場所 std::optional<int> go(int now,char c){ if(trie[now].count(c)){ return trie[now][c]; }else if(now==root) return root; else return {}; } void bfs(){ failure=std::vector<int>(trie.size(),0); dist=std::vector<int>(trie.size(),-1); std::queue<int> que; dist[root]=0; que.push(root); while(!que.empty()){ int now=que.front(); que.pop(); for(auto [c,to]:trie[now]){ //nowのキーc,toを取り出す //trie[now][c]=toとなる if(now!=root){ int f=failure[now];//nowで失敗した場合に行きつく場所 while(!go(f,c)){ f=failure[f]; } //go(f,c).firstがtrueつまり状態fの次に文字cで行ける場所がある もしくはfがroot failure[to]=*go(f,c); for(const auto& string:output[failure[to]]){ //ノードfailure[to]で終わる文字列たちをtoにもいれる output[to].push_back(string); } } que.push(to); dist[to]=dist[now]+1; } } } }; int main(){ string S; cin>>S; int M; cin>>M; ans=vector<int>(M,0); Aho_Corasick aho; vector<string> C(M); for(int i=0;i<M;i++){ cin>>C[i]; aho.add(C[i]); } aho.bfs(); aho.match(S); ll cntans=0; for(int i=0;i<M;i++){ cntans+=ans[i]; } cout<<cntans<<endl; }