結果

問題 No.430 文字列検索
ユーザー beetbeet
提出日時 2021-01-22 17:50:47
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 3,273 bytes
コンパイル時間 1,883 ms
コンパイル使用メモリ 210,136 KB
実行使用メモリ 8,132 KB
最終ジャッジ日時 2024-11-10 00:52:47
合計ジャッジ時間 4,705 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// verification-helper: PROBLEM https://yukicoder.me/problems/1013

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
template<size_t X>
struct Trie{
  struct Node{
    char c;
    array<int, X> nxt;
    vector<int> idxs;
    int idx;
    Node(char c):c(c),idx(-1){fill(nxt.begin(),nxt.end(),-1);}
  };

  using F = function<int(char)>;
  vector<Node> vs;
  F conv;

  Trie(F conv,char c='$'):conv(conv){vs.emplace_back(c);}
  Trie(char start,char c='$'):Trie([=](char a){return a-start;},c){}

  inline int &next(int i,int j){
    return vs[i].nxt[j];
  }

  void add(const string &s,int x){
    int pos=0;
    for(int i=0;i<(int)s.size();i++){
      int k=conv(s[i]);
      if(~next(pos,k)){
        pos=next(pos,k);
        continue;
      }
      int npos=vs.size();
      next(pos,k)=npos;
      vs.emplace_back(s[i]);
      pos=npos;
    }
    vs[pos].idx=x;
    vs[pos].idxs.emplace_back(x);
  }

  int find(const string &s){
    int pos=0;
    for(int i=0;i<(int)s.size();i++){
      int k=conv(s[i]);
      if(next(pos,k)<0) return -1;
      pos=next(pos,k);
    }
    return pos;
  }

  int move(int pos,char c){
    assert(pos<(int)vs.size());
    return pos<0?-1:next(pos,conv(c));
  }

  int size(){return vs.size();}

  int idx(int pos){
    return pos<0?-1:vs[pos].idx;
  }

  vector<int> idxs(int pos){
    return pos<0?vector<int>():vs[pos].idxs;
  }

};

template<size_t X, bool heavy>
struct AhoCorasick : Trie<X+1>{
  using super = Trie<X+1>;
  using super::super, super::next, super::size;
  using super::vs, super::conv;

  vector<int> cnt;
  void build(){
    int n=vs.size();
    cnt.resize(n);
    for(int i=0;i<n;i++){
      if(heavy) sort(vs[i].idxs.begin(),vs[i].idxs.end());
      cnt[i]=vs[i].idxs.size();
    }

    queue<int> que;
    for(int i=0;i<(int)X;i++){
      if(~next(0,i)){
        next(next(0,i),X)=0;
        que.emplace(next(0,i));
      }else{
        next(0,i)=0;
      }
    }

    while(!que.empty()){
      auto &x=vs[que.front()];
      int fail=x.nxt[X];

      cnt[que.front()]+=cnt[fail];
      que.pop();

      for(int i=0;i<(int)X;i++){
        int &nx=x.nxt[i];
        if(nx<0){
          nx=next(fail,i);
          continue;
        }
        que.emplace(nx);
        next(nx,X)=next(fail,i);
        if(heavy){
          auto &idx=vs[nx].idxs;
          auto &idy=vs[next(fail,i)].idxs;
          vector<int> idz;
          set_union(idx.begin(),idx.end(),
                    idy.begin(),idy.end(),
                    back_inserter(idz));
          idx=idz;
        }
      }
    }
  }

  int count(int pos){
    return cnt[pos];
  }

  int match(string s){
    int res=0,pos=0;
    for(auto &c:s){
      pos=next(pos,conv(c));
      res+=count(pos);
    }
    return res;
  }

  vector<int> frequency(string s){
    vector<int> res(size(),0);
    int pos=0;
    for(auto &c:s){
      pos=next(pos,conv(c));
      res[pos]++;
    }
    for(int i=size()-1;i;i--)
      res[vs[i].nxt[X]]+=res[i];
    return res;
  }
};

#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  AhoCorasick<26, false> aho('A');
  string s;
  cin>>s;
  int m;
  cin>>m;
  for(int i=0;i<m;i++){
    string c;
    cin>>c;
    aho.add(c,i);
  }

  cout<<aho.match(s)<<endl;
  return 0;
}
0