結果

問題 No.430 文字列検索
ユーザー HIcoderHIcoder
提出日時 2024-08-25 12:36:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 28 ms / 2,000 ms
コード長 3,932 bytes
コンパイル時間 1,442 ms
コンパイル使用メモリ 146,200 KB
実行使用メモリ 10,440 KB
最終ジャッジ日時 2024-11-10 01:13:03
合計ジャッジ時間 2,174 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 28 ms
10,440 KB
testcase_02 AC 10 ms
5,248 KB
testcase_03 AC 9 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 6 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 19 ms
6,844 KB
testcase_12 AC 20 ms
7,588 KB
testcase_13 AC 20 ms
7,584 KB
testcase_14 AC 16 ms
6,320 KB
testcase_15 AC 13 ms
5,476 KB
testcase_16 AC 12 ms
5,480 KB
testcase_17 AC 12 ms
5,484 KB
権限があれば一括ダウンロードができます

ソースコード

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