#1165522 (C++23) No.430 文字列検索

• 問題: No.430 文字列検索
• ユーザー: hidehic0
• 提出日時: 2026-05-19 12:06:33
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 16 ms / 2,000 ms
• コード長: 7,525 bytes
• コンパイル時間: 3,753 ms
• コンパイル使用メモリ: 347,584 KB
• 実行使用メモリ: 8,252 KB
• 最終ジャッジ日時: 2026-05-19 12:06:39
• 合計ジャッジ時間: 5,637 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

ファイルパターン	結果
sample	AC * 4
other	AC * 14

ソースコード

#line 1 "test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/430

#include <bits/stdc++.h>
using namespace std;
#line 7 "/home/hidehic0/src/github.com/hidehic0/library_cpp/templates/alias.hpp"

template <class T> using VC = std::vector<T>;
template <class T>
using rpriority_queue = std::priority_queue<T, VC<T>, std::greater<T>>;
using ll = long long;
using ld = long double;
using pii = std::pair<ll, ll>;
using vi = VC<ll>;
using vvi = VC<vi>;
using vvvi = VC<vvi>;
using vb = VC<bool>;
using vvb = VC<vb>;
using vf = VC<double>;
using vvf = VC<vf>;
using vpii = VC<pii>;
using vvpii = VC<vpii>;
using si = std::set<ll>;
using spii = std::set<pii>;
using mii = std::map<ll, ll>;
const std::string upperlist = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const std::string lowerlist = "abcdefghijklmnopqrstuvwxyz";
#define mp make_pair
#define dms << " " <<

constexpr int MOD998 = 998244353;
#line 4 "/home/hidehic0/src/github.com/hidehic0/library_cpp/templates/macro.hpp"

// 引数の長さで内容が変わるrep 参考: https://trap.jp/post/1224
#define overload4(a, b, c, d, ...) d
#define _rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rep(...) overload4(__VA_ARGS__, REP, _rep)(__VA_ARGS__)
#define _rrep(i, n) for (int i = n - 1; i >= 0; i--)
#define RREP(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); i--)
#define rrep(...) overload4(__VA_ARGS__, RREP, _rrep)(__VA_ARGS__)

#define all(a) (a).begin(), (a).end()

template <typename T> bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T> bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

template <typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
  is >> p.first >> p.second;
  return is;
}

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 (int i = 0; i < (int)v.size(); i++) {
    os << v[i] << (i + 1 == v.size() ? "" : " ");
  }
  return os;
}

// pythonのprintライクな関数 参考:
// https://nyaannyaan.github.io/library/template/inout.hpp
inline void out() { std::cout << std::endl; }
template <typename T, typename... U, char sep = ' '>
void out(const T &t, const U &...u) {
  std::cout << t;

  if (sizeof...(u))
    std::cout << sep;

  out(u...);
}

// cinの短縮関数 参考: https://nyaannyaan.github.io/library/template/inout.hpp
inline void in() {}
template <typename T, class... U> void in(T &t, U &...u) {
  std::cin >> t;
  in(u...);
}

template <typename T> inline T ceil_div(T a, T b) { return (a + b - 1) / b; }
template <typename T> inline T mod_pow(T a, T n, T mod) {
  T res = 1;
  while (n) {
    if (n % 2 != 0) {
      res *= a;
      res %= mod;
    }

    a *= a;
    a %= mod;

    n >>= 1;
  }

  return res;
}
template <typename T> inline T minus_mod(T a, T b) { return ((a % b) + b) % b; }

template <typename T> void apply_vec(std::vector<T> &v, T (*fn)(T)) {
  for (int i = 0; i < v.size(); i++)
    v[i] = fn(v[i]);
}
#line 7 "test.cpp"

#line 3 "/home/hidehic0/src/github.com/hidehic0/library_cpp/string/trie.hpp"

/*!
 * @struct Trie
 * Trie木構造体 使う文字は[margin,margin+char_size)の範囲でないといけない
 * @note
 * 参考: https://nyaannyaan.github.io/library/string/trie.hpp
 */
template <size_t char_size = 26, char margin = 'a'> struct Trie {
  struct Node {
    std::array<int, char_size> nxt;
    std::vector<int> accepts;

    char key;
    int child_accepts = 0;

    Node(char c) : key(c) { fill(nxt.begin(), nxt.end(), -1); };
  };

  std::vector<Node> nodes;

  Trie(char root = '$') { nodes.emplace_back(root); }

  inline int get_next(int i, int j) { return nodes[i].nxt[j]; }

  void add(std::string S, int id = -1) {
    int cur = 0;

    for (char s : S) {
      int k = s - margin;

      assert(0 <= k && k < char_size);

      if (~get_next(cur, k)) {
        cur = get_next(cur, k);
        continue;
      }

      int nxt = nodes.size();

      nodes[cur].nxt[k] = nxt;
      nodes.emplace_back(s);
      nodes[nxt].child_accepts++;

      cur = nxt;
    }

    nodes[cur].accepts.emplace_back(id == -1 ? nodes[0].child_accepts++ : id);
  }

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

/*!
 * @file string/trie.hpp
 * @brief trie木のstructが置いてある
 * @auther hidehic0
 */
#line 5 "/home/hidehic0/src/github.com/hidehic0/library_cpp/string/aho-corasick.hpp"

/*!
 * @struct AhoCorasick
 * string/trie.hppのTrie構造体を継承している
 * trieの各ノードに対して、存在しない子ノードから、子を連結した文字列のprefixの中で長さが最大のノードに繋ぐオートマトンを作成する
 * テンプレート引数のheavyをtrueにすると、各ノードに対してマッチする文字列の列を管理できる
 * falseにすると個数のみ
 * build関数でオートマトンを作成する O(S)
 */

template <size_t char_size = 26, int margin = 'a', bool heavy = true>
struct AhoCorasick : Trie<char_size + 1, margin> {
  using TRIE = Trie<char_size + 1, margin>;
  using TRIE::get_next;

  std::vector<int> correct;

  /*!
   * @fn
   * trieの各ノードに対して、存在しない子ノードから、子を連結した文字列のprefixの中で長さが最大のノードに繋ぐオートマトンを作成する
   * 計算量は追加された文字列の長さの和をSとしてO(S)
   */
  void build() {
    correct.resize(this->nodes.size());

    for (int i = 0; i < this->size(); i++) {
      correct[i] = this->nodes[i].accepts.size();
    }

    std::queue<int> que;

    for (int k = 0; k < char_size; k++) {
      if (~get_next(0, k)) {
        this->nodes[get_next(0, k)].nxt[char_size] = 0;
        que.emplace(get_next(0, k));
      } else {
        this->nodes[0].nxt[k] = 0;
      }
    }

    while (!que.empty()) {
      auto &x = this->nodes[que.front()];
      int fail = x.nxt[char_size];

      correct[que.front()] += correct[fail];

      que.pop();

      for (int k = 0; k < char_size; k++) {
        int &nxt = x.nxt[k];

        if (nxt < 0) {
          nxt = get_next(fail, k);
          continue;
        }

        que.emplace(nxt);
        this->nodes[nxt].nxt[char_size] = get_next(fail, k);

        if (heavy) {
          auto &accept_x = this->nodes[nxt].accepts;
          auto &accept_y = this->nodes[get_next(fail, k)].accepts;

          std::vector<int> accept;

          set_union(accept_x.begin(), accept_x.end(), accept_y.begin(),
                    accept_y.end(), std::back_inserter(accept));

          accept_x = accept;
        }
      }
    }
  }

  std::pair<int, int> move(const char &c, int now = 0) {
    now = get_next(now, c - margin);

    return {correct[now], now};
  }
  std::pair<int, int> move(const std::string &s, int now = 0) {
    int res = 0;

    for (auto &c : s) {
      auto [cnt, nxt] = move(c, now);
      res += cnt, now = nxt;
    }

    return {res, now};
  }
};

/*!
 * @file string/aho-corasick.hpp
 * @brief AhoCorasick構造体が置いてある
 * @auther hidehic0
 * @date 2026-05-19
 */
#line 9 "test.cpp"

int main() {
  string S;
  ll N;
  in(S, N);

  AhoCorasick<26, 'A'> AH;

  rep(i, N) {
    string T;
    in(T);

    AH.add(T, i);
  }
  AH.build();

  cout << AH.move(S, 0).first << "\n";
}