fork download
copy 
  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. using pii = pair<int, int>;
  8. const int N = 1e6 + 5;
  9. const int A = 2e6 +6;
  10. int q;
  11. struct query {
  12.     int t, id;
  13.     string s;
  14. } Q[N];
  15. namespace sub1 {
  16. using HASH = unsigned long long;
  17. using pih = pair<int, HASH>;
  18. const HASH BASE = 3;
  19. HASH T[A], POW[A];
  20. HASH getHash(int l, int r) {
  21.     return T[r] - T[l - 1] * POW[r - l + 1];
  22. }
  23. bool checksub() {
  24.     int cnt1 = 0, cnt2 = 0;
  25.     for (int i = 1; i <= q; i++) {
  26.         if (Q[i].t == 0) cnt1++;
  27.         else cnt2 += (int)Q[i].s.size();
  28.     }
  29.     return (long long) cnt1 * cnt2 <= 200000000;
  30. }
  31. void solve() {
  32.     vector<pih> S;
  33.     POW[0] =1;
  34.     for (int i = 1; i < A; i++) POW[i] = POW[i - 1] * BASE;
  35.     for (int id = 1; id <= q; id++) {
  36.         if (Q[id].t == 0) {
  37.             int n = Q[id].s.size();
  38.             HASH h = 0;
  39.             for (char c: Q[id].s) {
  40.                 h = h * BASE + (c - '0' + 1);
  41.             }
  42.             S.push_back({n, h});
  43.         }
  44.         else {
  45.             int n = Q[id].s.size();
  46.             for (int i = 1; i <= n; i++) T[i] = T[i - 1] * BASE + (Q[id].s[i - 1] -'0' + 1);
  47.             int ans = 0;
  48.             for (pih item: S) {
  49.                 for (int i = 1; i + item.ft - 1 <= n; i++) {
  50.                     if (getHash(i, i + item.ft - 1) == item.sc) ans++;
  51.                 }
  52.             }
  53.             cout << ans << "\n";
  54.         }
  55.     }
  56. }
  57. };
  58.  
  59. namespace sub2{
  60. //Chep Code Aho
  61. struct AhoCorasick {
  62.     static const int SIGMA = 2;
  63.     int base;
  64.     struct Node {
  65.         array<int, SIGMA> next{};
  66.         int link = 0;
  67.         int out = 0;
  68.         Node() { next.fill(-1); }
  69.     };
  70.  
  71.     vector<Node> t;
  72.     vector<int> term_node, bfs_order;
  73.  
  74.     AhoCorasick(int baseChar = 'a') : base(baseChar) {
  75.         t.emplace_back();
  76.         t[0].link = 0;
  77.     }
  78.  
  79.  
  80.     int add(const string& s) {
  81.         int v = 0;
  82.         for (char ch : s) {
  83.             int c = ch - base;
  84.             if (c < 0 || c >= SIGMA) {
  85.                 continue;
  86.             }
  87.             if (t[v].next[c] == -1) {
  88.                 t[v].next[c] = (int)t.size();
  89.                 t.emplace_back();
  90.             }
  91.             v = t[v].next[c];
  92.         }
  93.         t[v].out += 1;
  94.         term_node.push_back(v);
  95.         return (int)term_node.size() - 1;
  96.     }
  97.  
  98.     void build() {
  99.         queue<int> q;
  100.         for (int c = 0; c < SIGMA; ++c) {
  101.             int u = t[0].next[c];
  102.             if (u != -1) {
  103.                 t[u].link = 0;
  104.                 q.push(u);
  105.             } else {
  106.                 t[0].next[c] = 0;
  107.             }
  108.         }
  109.         bfs_order.clear();
  110.         while (!q.empty()) {
  111.             int v = q.front(); q.pop();
  112.             bfs_order.push_back(v);
  113.             int link = t[v].link;
  114.             t[v].out += t[link].out; 
  115.             for (int c = 0; c < SIGMA; ++c) {
  116.                 int u = t[v].next[c];
  117.                 if (u != -1) {
  118.                     t[u].link = t[link].next[c];
  119.                     q.push(u);
  120.                 } else {
  121.                     t[v].next[c] = t[link].next[c];
  122.                 }
  123.             }
  124.         }
  125.     }
  126.  
  127.     long long count_total(const string& s) const {
  128.         long long ans = 0;
  129.         int v = 0;
  130.         for (char ch : s) {
  131.             int c = ch - base;
  132.             if (c < 0 || c >= SIGMA) { v = 0; continue; }
  133.             v = t[v].next[c];
  134.             ans += t[v].out;
  135.         }
  136.         return ans;
  137.     }
  138. };
  139. int ans[N];
  140. void DnC(int l, int r){
  141.     if(l >= r) return;
  142.     int mid = l + r >> 1;
  143.     AhoCorasick ac('0');
  144.     vector<int> updates, queries;
  145.     for(int i = l; i <= mid; ++i){
  146.         if(Q[i].t == 0) ac.add(Q[i].s);
  147.     }
  148.     ac.build();
  149.     for(int i = mid + 1; i <= r; ++i){
  150.         if(Q[i].t == 1) ans[i] += ac.count_total(Q[i].s);
  151.     }
  152.     DnC(l, mid);
  153.     DnC(mid + 1, r);
  154. }
  155.  
  156. void solve() {
  157.     DnC(1, q);
  158.     for (int i = 1; i <= q; i++) if (Q[i].t == 1) cout << ans[i] << '\n';
  159. }
  160. };
  161.  
  162. signed main() {
  163.     cin.tie(NULL)->sync_with_stdio(false); cout.tie(NULL);
  164.     if(ifstream("VIRUS.inp")) {
  165.         freopen("VIRUS.inp", "r", stdin);
  166.         freopen("VIRUS.out", "w", stdout);
  167.     }
  168.     cin >> q;
  169.     for (int i = 1; i <= q; i++) {
  170.         cin >> Q[i].t >> Q[i].s;
  171.         Q[i].id = i;
  172.     }
  173.     // if (sub1::checksub()) return sub1::solve(), 0;
  174.     return sub2::solve(), 0;
  175.     return 0;
  176. }
Success #stdin #stdout 0.02s 50844KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wxvkio
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!