結果

問題 No.430 文字列検索
ユーザー beetbeet
提出日時 2021-01-22 17:52:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 3,287 bytes
コンパイル時間 2,345 ms
コンパイル使用メモリ 211,300 KB
実行使用メモリ 8,288 KB
最終ジャッジ日時 2023-08-27 11:57:52
合計ジャッジ時間 3,481 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 9 ms
8,288 KB
testcase_02 AC 5 ms
4,660 KB
testcase_03 AC 4 ms
4,532 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 8 ms
5,560 KB
testcase_12 AC 8 ms
5,652 KB
testcase_13 AC 8 ms
5,608 KB
testcase_14 AC 7 ms
5,616 KB
testcase_15 AC 6 ms
5,576 KB
testcase_16 AC 6 ms
5,552 KB
testcase_17 AC 6 ms
5,628 KB
権限があれば一括ダウンロードができます

ソースコード

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);
  }
  aho.build();
  cout<<aho.match(s)<<endl;
  return 0;
}
0