結果

問題 No.430 文字列検索
コンテスト
ユーザー ferin
提出日時 2018-10-08 18:10:35
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,314 bytes
コンパイル時間 1,273 ms
コンパイル使用メモリ 163,752 KB
最終ジャッジ日時 2024-11-10 00:20:08
合計ジャッジ時間 1,607 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:19:1: error: ‘make_v’ function uses ‘auto’ type specifier without trailing return type
   19 | auto make_v(size_t a,Ts... ts) {
      | ^~~~
main.cpp:19:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’

ソースコード

diff # 

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) is >> x; return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;
 
// 文字の種類数をtemplate引数で渡す
template <int types = 26>
struct AhoCorasick {
  // trie木のnode
  struct node {
    int fail;
    vector<int> next;
    vector<int> matched;
    node() : fail(-1), next(types, -1) {}
  };
 
  // node の集合
  vector<node> nodes;
  // 辞書の種類数, trie木の根
  int sz, root;
  // 文字と数字の対応付けをする関数
  using F = function<int(char)>;
  F trans;
 
  // 初期化
  AhoCorasick() {}
  AhoCorasick(vector<string> pattern, F f = [](char c){return c-'a';}) 
    : sz(pattern.size()), root(0)
  {
    nodes.resize(1);
    trans = f;
    build(pattern);
  }
  // vectorを結合
  vector<int> unite(const vector<int> &a, const vector<int> &b) {
    vector<int> ret;
    set_union(ALL(a), ALL(b), back_inserter(ret));
    return ret;
  }
  // 文字列集合patternからtrie木っぽいオートマトンを作成
  void build(vector<string> pattern) {
    int now;
    nodes[root].fail = root;
    REP(i, pattern.size()) {
      now = root;
      for(const auto &c: pattern[i]) {
        if(nodes[now].next[trans(c)] == -1) {
          nodes.push_back(node());
          nodes[now].next[trans(c)] = nodes.size() - 1;
        }
        now = nodes[now].next[trans(c)];
      }
      nodes[now].matched.push_back(i);
    }
 
    queue<int> que;
    REP(i, types) {
      if(nodes[root].next[i] == -1) {
        nodes[root].next[i] = root;
      } else {
        nodes[nodes[root].next[i]].fail = root;
        que.push(nodes[root].next[i]);
      }
    }
    while(que.size()) {
      now = que.front(); que.pop();
      REP(i, types) {
        if(nodes[now].next[i] != -1) {
          int nxt = nodes[now].fail;
          while(nodes[nxt].next[i] == -1) nxt = nodes[nxt].fail;
          int nxt_tmp = nodes[now].next[i];
          nodes[nxt_tmp].fail = nodes[nxt].next[i];
          nodes[nxt_tmp].matched
            = unite(nodes[nxt_tmp].matched, nodes[nodes[nxt].next[i]].matched);
          que.push(nxt_tmp);
        }
      }
    }
  }
  // 一文字ずつ照合していく
  int next(int p, const char c) {
    while(nodes[p].next[trans(c)] == -1) p = nodes[p].fail;
    return nodes[p].next[trans(c)];
  }
  // 文字列s中に辞書と一致する部分列がどれだけあるか
  vector<int> match(const string s) {
    vector<int> res(sz);
    int now = root;
    for(auto c : s) {
      now = next(now, c);
      for(auto i : nodes[now].matched) res[i]++;
    }
    return res;
  }
};
 
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int m;
  string s;
  cin >> s >> m;
  vector<string> c(m);
  cin >> c;

  auto trans = [&](char c){ return c-'A'; };
  AhoCorasick<26> aho(c, trans);

  auto ret = aho.match(s);
  
  int ans = 0;
  for(auto i: ret) ans += i;
  cout << ans << endl;

  return 0;
}
0