結果

問題 No.430 文字列検索
ユーザー igeee
提出日時 2025-08-17 17:07:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 7,937 bytes
コンパイル時間 6,098 ms
コンパイル使用メモリ 334,164 KB
実行使用メモリ 7,988 KB
最終ジャッジ日時 2025-08-17 17:07:59
合計ジャッジ時間 6,970 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rrep(i,start,end) for (ll i = start;i >= (ll)(end);i--)
#define repn(i,end) for(ll i = 0; i <= (ll)(end); i++)
#define reps(i,start,end) for(ll i = start; i < (ll)(end); i++)
#define repsn(i,start,end) for(ll i = start; i <= (ll)(end); i++)
#define each(p,a) for(auto &p:a)
typedef vector<ll> vll;
typedef vector<pair<ll ,ll>> vpll;
typedef vector<vector<ll>> vvll;
typedef set<ll> sll;
typedef map<ll , ll> mpll;
typedef pair<ll ,ll> pll;
typedef tuple<ll , ll , ll> tpl3;
#define LL(...) ll __VA_ARGS__; input(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; input(__VA_ARGS__)
#define Str(...) string __VA_ARGS__; input(__VA_ARGS__)
#define Ch(...) char __VA_ARGS__; input(__VA_ARGS__)
#define all(a)  (a).begin(),(a).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define sz(x) (ll)x.size()
// << std::fixed << std::setprecision(10)
const ll INF = 1LL << 60;
const ld EPS = 1e-9;
 
ll lceil(ll a,ll b){if(a%b==0){return a/b;}if(a>=0){return (a/b)+1;}else{return -((-a)/b);}}
ll lfloor(ll a,ll b){if(a%b==0){return a/b;}if(a>=0){return (a/b);}else{return -((-a)/b)-1;}}
inline ll positive_mod(ll a,ll m){return (a % m + m)%m;}
inline ll popcnt(ull a){ return __builtin_popcountll(a);}
//0indexed
inline ll topbit(ll a){assert(a != 0);return 63 - __builtin_clzll(a);}
inline ll smlbit(ll a){assert(a != 0);return __builtin_ctzll(a);}
template<class T> bool chmin(T& a, T b){if(a > b){a = b;return true;}return false;}
template<class T> bool chmax(T& a, T b){if(a < b){a = b;return true;}return false;}
template<typename T> std::istream &operator>>(std::istream&is,std::vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T> std::ostream &operator<<(std::ostream&os,const std::vector<T>&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;}
template<typename T1, typename T2>std::ostream &operator<< (std::ostream &os, std::pair<T1,T2> p){os << "{" << p.first << "," << p.second << "}";return os;}
template<class... T>void input(T&... a){(cin >> ... >> a);}
void print(){cout << endl;}
template<class T, class... Ts>void print(const T& a, const Ts&... b){cout << a;((cout << ' ' << b), ...);cout << endl;}
template<class T> void pspace(const T& a){ cout << a << ' ';}
void perr(){cerr << endl;}
template<class T, class... Ts>void perr(const T& a, const Ts&... b){cerr << a;((cerr << ' ' << b), ...);cerr << endl;}
void yes(bool i = true){ return print(i?"yes":"no"); }
void Yes(bool i = true){ return print(i?"Yes":"No"); }
void YES(bool i = true){ return print(i?"YES":"NO"); }
template <class T> vector<T> &operator++(vector<T> &v) {for(auto &e : v) e++;return v;}
template <class T> vector<T> operator++(vector<T> &v, signed) {auto res = v;for(auto &e : v) e++;return res;}
template <class T> vector<T> &operator--(vector<T> &v) {for(auto &e : v) e--;return v;}
template <class T> vector<T> operator--(vector<T> &v, signed) {auto res = v;for(auto &e : v) e--;return res;}
//grid探索用
vector<ll> _ta = {0,0,1,-1,1,1,-1,-1};
vector<ll> _yo = {1,-1,0,0,1,-1,1,-1};
bool isin(ll now_i,ll now_j,ll h,ll w){return (0<=now_i && now_i < h && 0 <= now_j && now_j < w);}
  
ll lpow(ll x,ll n){ll ans = 1;while(n >0){if(n & 1)ans *= x;x *= x;n >>= 1;}return ans;}
ll Modlpow(ll x,ll n,ll m){ll ans = 1;ll a = x%m;while(n >0){if(n & 1){ans *= a;ans%= m;}a *= a;a %= m;n >>= 1;}return ans;} 
const ll MOD9 = 998244353LL;
const ll MOD10 = 1000000007LL;




/**
 * @struct AhoCorasick
 * @brief 文字列(text)と文字列集合(words)があるときにtext内に各wordがいくつ現れるかの計算
 * 
 * @details
 * Trie木を普通に構築(insert)した後、BFSでfailの計算(set_fail)
 * set_fail()ではTrie木上の各nodeがが末尾となるwordの集合がacceptになるように更新
 * 
 * @note 
 * fail : 今見ている文字列の接尾辞でTie木上に登録されているキーワードの接頭辞のうち最長のもの
 * 
 * @complexity
 * 構築 O(Σ|words[i]|) wordsの文字列長の合計
 * 検索 O(|text| + 出現数)
 * 
 * @ref
 * https://kntychance.hatenablog.jp/entry/2024/07/28/144203#fail-%E3%81%AE%E5%89%8D%E8%A8%88%E7%AE%97
 * https://ei1333.github.io/luzhiled/snippets/string/aho-corasick.html
 * 
 * @vefify
 * https://atcoder.jp/contests/abc362/submissions/68592335
 */
template<int char_size,int base>
struct AhoCorasick {
  struct Node{
    vector<int> next;//子のidx,存在しないなら-1
    vector<int> accept;//その頂点が末端となる文字列のid
    int c; //baseからの距離
    int common; //その頂点を何個の文字列が共有しているか
    Node(int _c){
      c = _c;
      common = 0;
      next.assign(char_size+1,-1);//next[char_size]はfailの行き先
    }
  };

  vector<Node> nodes;
  int root;
  int fail = char_size;
  int words_size;//何個の文字列を登録したか

  AhoCorasick(vector<string> &words){
    root = 0;
    words_size = (int)words.size();
    nodes.push_back(Node(root));
    for(const auto &word:words){ // Trie木上にwords内の文字列を配置
      insert(word);
    }
    set_fail();
  }

  void insert(const string &word,int wordid){
    int nodeid = 0;
    rep(i,word.size()){
      int c = (int)(word[i] - base);
      int nextid = nodes[nodeid].next[c];
      if(nextid == -1){//次の頂点がない
        nextid = nodes.size();
        nodes.push_back(Node(nodes[nodeid].c + 1)); //rootからの距離をNodeに持たせる.参考元から変更した
        nodes[nodeid].next[c] = nextid;
      }
      nodes[nodeid].common++;
      nodeid = nextid;
    }
    nodes[nodeid].common++;
    nodes[nodeid].accept.push_back(wordid);
  }
  void insert(const string &word){
    insert(word,nodes[0].common);
  }

  void set_fail(){
    queue<int> que;
    //rootの処理
    for(int i = 0;i < char_size;++i){
      if(nodes[root].next[i]!= -1){
        nodes[nodes[root].next[i]].next[fail] = root;
        que.push(nodes[root].next[i]);
      }else{
        nodes[root].next[i] = 0;
      }
    }
    nodes[root].next[fail] = root;
    while(!que.empty()){
      ll now = que.front();
      que.pop();
      //childsのfailを計算
      for(int i = 0;i < char_size;++i)if(nodes[now].next[i] != -1){
        int nid = nodes[now].next[fail];
        while(nodes[nid].next[i]== -1){
          nid = nodes[nid].next[fail];
        }
        nodes[nodes[now].next[i]].next[fail] = nodes[nid].next[i];
        que.push(nodes[now].next[i]);
        //acceptの追加
        vector<int> naccept;
        auto &u = nodes[nodes[now].next[i]].accept;
        auto &v = nodes[nodes[nid].next[i]].accept; 
        set_union(u.begin(),u.end(),v.begin(),v.end(),back_inserter(naccept));
        nodes[nodes[now].next[i]].accept = naccept;
      }
    }
  }
  
  //text内に各文字列がそれぞれ何回現れるか
  vector<ll> count(string& text){
    vector<int> visited_cnt(nodes.size());//各nodeを何回訪れたか
    int id = 0;
    for(const char &p:text){
      int c = (int)(p - base);
      if(nodes[id].next[c] != -1){
        id = nodes[id].next[c];
        visited_cnt[id]++;
      }else{
        while(nodes[nodes[id].next[fail]].next[c] == -1){
          id = nodes[id].next[fail];
        }
        id = nodes[nodes[id].next[fail]].next[c];
        visited_cnt[id]++;
      }
    }
    vector<ll> ret(words_size);
    for(int i = 0;i < (int)nodes.size();++i){
      for(auto &p:nodes[i].accept){
        ret[p] += (ll)visited_cnt[i];
      }
    }
    return ret;
  }
};
 
int main(){
  ios::sync_with_stdio(false);cin.tie(nullptr);
  Str(s);
  LL(q);
  vector<string > t(q);cin >> t;
  AhoCorasick<26,'A'> aho(t);
  vector<ll> ret =aho.count(s);
  cout << reduce(all(ret)) << endl;
}
0