結果

問題 No.430 文字列検索
ユーザー HIcoder
提出日時 2024-08-25 12:36:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 3,932 bytes
コンパイル時間 1,563 ms
コンパイル使用メモリ 141,820 KB
最終ジャッジ日時 2025-02-24 00:43:35
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<cassert>
#include<random>
#include<set>
#include<map>
#include<cassert>
#include<unordered_map>
#include<bitset>
#include<numeric>
#include<algorithm>
#include<optional>
using namespace std;
typedef long long ll;
const int inf=1<<30;
const ll INF=1LL<<62;
typedef pair<int,ll> P;
typedef pair<int,P> PP; 
const ll MOD=998244353;



ll ans=0;

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=0;
        
        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);

            ans+=output[now].size();

            // for(const auto& x:output[now]){
            //     //ノードnowで終わる場合
            //     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;
    vector<string> C(M);
    for(int i=0;i<M;i++){
        cin>>C[i];
    }
    
    Aho_Corasick ac;
    for(int i=0;i<M;i++){
        ac.add(C[i]);
    }

    ac.bfs();
    ac.match(S);

    cout<<ans<<endl;



    
    
}
0