結果

問題 No.430 文字列検索
コンテスト
ユーザー shinchan
提出日時 2025-10-29 17:09:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 4,715 bytes
コンパイル時間 3,322 ms
コンパイル使用メモリ 291,536 KB
実行使用メモリ 8,896 KB
最終ジャッジ日時 2025-10-29 17:09:45
合計ジャッジ時間 4,779 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define all(v) (v).begin(),(v).end()
#define pb emplace_back
#define rep(i, n) for(int i=0;i<(n);i++)
#define foa(e, v) for(auto& e : v)
#define dout(a) cout<<fixed<<setprecision(10)<<a<<'\n';
#define Cout(a) cout<<a<<'\n';

using ll = long long;
using ld = long double;
using Int = __int128;
template <class T> using pqr = priority_queue<T, vector<T>, greater<T>>;

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {
    bool compare = a < b;
    if(compare) a = b;
    return compare;
}
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {
    bool compare = a > b;
    if(compare) a = b;
    return compare;
}
template <typename T> inline T back(std::set<T> &s) {
    return *s.rbegin();
}
template <typename T> inline T back(std::multiset<T> &s) {
    return *s.rbegin();
}
template <typename T> inline T pop_back(std::set<T> &s) {
    auto it = prev(s.end());
    T val = *it;
    s.erase(it); 
    return val;
}
template <typename T> inline T pop_back(std::multiset<T> &s) {
    auto it = prev(s.end());
    T val = *it;
    s.erase(it); 
    return val;
}

const int dy[8] = {-1, 0, 0, 1, 1, -1, 1, -1};
const int dx[8] = {0, -1, 1, 0, -1, -1, 1, 1};

const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (3LL << 59);
const int inf = 1 << 30;
const char br = '\n';

template<int char_size> struct TrieNode {
  int nxt[char_size];
  int exist;
  vector<int> accept;
  TrieNode() : exist(0) { memset(nxt, -1, sizeof(nxt)); }
};
template<int char_size, int margin> struct Trie {
  using Node = TrieNode<char_size>;
  vector<Node> nodes;
  int root;
  Trie() : root(0) { nodes.push_back(Node()); }
  void add(const string& str, int str_index, int node_index, int id) {
    if(str_index == size(str)) {
      nodes[node_index].accept.push_back(id);
    } else {
      const int c = str[str_index] - margin;
      if(nodes[node_index].nxt[c] == -1) {
        nodes[node_index].nxt[c] = size(nodes);
        nodes.push_back(Node());
      }
      add(str, str_index + 1, nodes[node_index].nxt[c], id);
      nodes[node_index].exist ++;
    }
  }
  void add(const string& str, int id = -1) {
    if(id == -1) id = nodes[0].exist;
    add(str, 0, 0, id);
  }
};
template<int char_size, int margin> struct AhoCorasick : Trie<char_size + 1, margin> {
  using Trie<char_size + 1, margin>::Trie;
  const int FAIL = char_size;
  vector<int> correct;
  void build(bool heavy = true) {
    correct.resize(this->nodes.size());
    for(int i = 0; i < size(this->nodes); ++i) { correct[i] = size(this->nodes[i].accept); }
    queue<int> que;
    for(int i = 0; i < char_size; ++i) {
      if(~this->nodes[0].nxt[i]) {
        this->nodes[this->nodes[0].nxt[i]].nxt[FAIL] = 0;
        que.emplace(this->nodes[0].nxt[i]);
      } else {
        this->nodes[0].nxt[i] = 0;
      }
    }
    while(!que.empty()) {
      auto& now = this->nodes[que.front()];
      int fail = now.nxt[FAIL];
      correct[que.front()] += correct[fail];
      que.pop();
      for(int i = 0; i < char_size; i++) {
        if(~now.nxt[i]) {
          this->nodes[now.nxt[i]].nxt[FAIL] = this->nodes[fail].nxt[i];
          if(heavy) {
            auto& u = this->nodes[now.nxt[i]].accept;
            auto& v = this->nodes[this->nodes[fail].nxt[i]].accept;
            vector<int> accept;
            set_union(all(u), all(v), back_inserter(accept));
            u = accept;
          }
          que.emplace(now.nxt[i]);
        } else {
          now.nxt[i] = this->nodes[fail].nxt[i];
        }
      }
    }
  }
  vector<int> match(const char& c, int now = 0) {
    vector<int> res;
    now = this->nodes[now].nxt[c - margin];
    for(auto& v : this->nodes[now].accept) res.push_back(v);
    return res;
  } 
  unordered_map<int, int> match(const string& str, int now = 0) {
    unordered_map<int, int> res, visit_cnt;
    for(auto& c : str) {
      now = this->nodes[now].nxt[c - margin];
      visit_cnt[now]++;
    }
    for(auto& [now, cnt] : visit_cnt) {
      for(auto& v : this->nodes[now].accept) res[v] += cnt;
    }
    return res;
  } 
  pair<ll, int> move(const char& c, int now = 0) {
    now = this->nodes[now].nxt[c - margin];
    return {correct[now], now};
  }
};

void solve() {
  string S;
  cin >> S;
  int M;
  cin >> M;
  AhoCorasick<26, 'A'> aho;
  for(int i = 0; i < M; i++) {
    string s;
    cin >> s;
    aho.add(s);
  }
  aho.build();
  ll sum = 0;
  int now = 0;
  foa(e, S) {
    auto [cnt, nx] = aho.move(e, now);
    sum += cnt;
    now = nx;
  }
  cout << sum << endl;
}

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

    int testcase = 1; 
    // cin >> testcase;
    while(testcase --) solve();

    return 0;
}
0