fork download 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7.  
  8. const int N = 1e6 + 5;
  9. int q, ans[N];
  10. struct query {
  11.     int t, id;
  12.     string s;
  13. } Q[N];
  14.  
  15. //Chep Code Aho
  16. struct AhoCorasick {
  17.     static const int SIGMA = 2;
  18.     int base;
  19.     struct Node {
  20.         array<int, SIGMA> next{};
  21.         int link = 0;
  22.         int out = 0;
  23.         Node() { next.fill(-1); }
  24.     };
  25.  
  26.     vector<Node> t;
  27.     vector<int> term_node, bfs_order;
  28.  
  29.     AhoCorasick(int baseChar = 'a') : base(baseChar) {
  30.         t.emplace_back();
  31.         t[0].link = 0;
  32.     }
  33.  
  34.     int add(const string& s) {
  35.         int v = 0;
  36.         for (char ch : s) {
  37.             int c = ch - base;
  38.             if (c < 0 || c >= SIGMA) {
  39.                 continue;
  40.             }
  41.             if (t[v].next[c] == -1) {
  42.                 t[v].next[c] = (int)t.size();
  43.                 t.emplace_back();
  44.             }
  45.             v = t[v].next[c];
  46.         }
  47.         t[v].out += 1;
  48.         term_node.push_back(v);
  49.         return (int)term_node.size() - 1;
  50.     }
  51.  
  52.     void build() {
  53.         queue<int> q;
  54.         for (int c = 0; c < SIGMA; ++c) {
  55.             int u = t[0].next[c];
  56.             if (u != -1) {
  57.                 t[u].link = 0;
  58.                 q.push(u);
  59.             } else {
  60.                 t[0].next[c] = 0;
  61.             }
  62.         }
  63.         bfs_order.clear();
  64.         while (!q.empty()) {
  65.             int v = q.front(); q.pop();
  66.             bfs_order.push_back(v);
  67.             int link = t[v].link;
  68.             t[v].out += t[link].out; 
  69.             for (int c = 0; c < SIGMA; ++c) {
  70.                 int u = t[v].next[c];
  71.                 if (u != -1) {
  72.                     t[u].link = t[link].next[c];
  73.                     q.push(u);
  74.                 } else {
  75.                     t[v].next[c] = t[link].next[c];
  76.                 }
  77.             }
  78.         }
  79.     }
  80.  
  81.     long long count_total(const string& s) const {
  82.         long long ans = 0;
  83.         int v = 0;
  84.         for (char ch : s) {
  85.             int c = ch - base;
  86.             if (c < 0 || c >= SIGMA) { v = 0; continue; }
  87.             v = t[v].next[c];
  88.             ans += t[v].out;
  89.         }
  90.         return ans;
  91.     }
  92. };
  93. void DnC(int l, int r){
  94.     if(l >= r) return;
  95.     int mid = l + r >> 1;
  96.     AhoCorasick ac('0');
  97.     vector<int> updates, queries;
  98.     for(int i = l; i <= mid; ++i){
  99.         if(Q[i].t == 0) ac.add(Q[i].s);
  100.     }
  101.     ac.build();
  102.     for(int i = mid + 1; i <= r; ++i){
  103.         if(Q[i].t == 1) ans[i] += ac.count_total(Q[i].s);
  104.     }
  105.     DnC(l, mid);
  106.     DnC(mid + 1, r);
  107. }
  108.  
  109. signed main() {
  110.     cin.tie(NULL)->sync_with_stdio(false); cout.tie(NULL);
  111.     if(ifstream("VIRUS.inp")) {
  112.         freopen("VIRUS.inp", "r", stdin);
  113.         freopen("VIRUS.out", "w", stdout);
  114.     }
  115.     cin >> q;
  116.     for (int i = 1; i <= q; i++) {
  117.         cin >> Q[i].t >> Q[i].s;
  118.     }
  119.  
  120.     DnC(1, q);
  121.     for (int i = 1; i <= q; i++) if (Q[i].t == 1) cout << ans[i] << '\n';
  122.     return 0;
  123. }
Success #stdin #stdout 0.01s 50976KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/pzpWht
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!