結果

問題 No.430 文字列検索
ユーザー HIcoderHIcoder
提出日時 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
コンパイル時間 2,208 ms
コンパイル使用メモリ 146,512 KB
実行使用メモリ 10,456 KB
最終ジャッジ日時 2024-02-09 17:50:04
合計ジャッジ時間 2,998 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 39 ms
10,456 KB
testcase_02 AC 12 ms
6,676 KB
testcase_03 AC 10 ms
6,676 KB
testcase_04 AC 1 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 1 ms
6,676 KB
testcase_07 AC 1 ms
6,676 KB
testcase_08 AC 6 ms
6,676 KB
testcase_09 AC 2 ms
6,676 KB
testcase_10 AC 2 ms
6,676 KB
testcase_11 AC 24 ms
7,244 KB
testcase_12 AC 24 ms
7,732 KB
testcase_13 AC 32 ms
7,732 KB
testcase_14 AC 18 ms
6,676 KB
testcase_15 AC 17 ms
6,676 KB
testcase_16 AC 14 ms
6,676 KB
testcase_17 AC 14 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;


    

}
0