pastebin

Paste Search Dynamic
Recent pastes
count
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define pii pair<ll, ll>
  4. #define st first
  5. #define nd second
  6. #define file "test"
  7. using namespace std;
  8. const long long INF = 1e18;
  9. const long long N = 2e6 + 20;
  10.  
  11. struct node {
  12.     int nxt[3], cnt, p;
  13.  
  14.     node (int par = -1) {
  15.         p = par;
  16.         nxt[0] = nxt[1] = nxt[2] = 0;
  17.         cnt = 0;
  18.     }
  19. };
  20.  
  21. vector <node> trie(1);
  22.  
  23. int q;
  24.  
  25. void insert(const string &s, int add) {
  26.     int pos = 0;
  27.     for (const char &ch: s) {
  28.         int u = ch - '0';
  29.         if (ch == '#') u = 2;
  30.         if (trie[pos].nxt[u] == 0) {
  31.             trie[pos].nxt[u] = trie.size();
  32.             trie.push_back(node(pos));
  33.         }
  34.  
  35.         pos = trie[pos].nxt[u];
  36.     }
  37.  
  38.     trie[pos].cnt += add; // if there is a vetor -> push once
  39. }
  40.  
  41. int p[N]; // suffix array
  42. ll sum[N];
  43.  
  44. void build() { // build an automaton-like data structure with no update
  45.     // itterate like bfs
  46.  
  47.     for (int i = 0; i < trie.size(); i ++) sum[i] = trie[i].cnt;
  48.  
  49.     queue <int> vi;
  50.  
  51.     vi.push(0);
  52.     while (vi.size()) {
  53.         int pos = vi.front(); vi.pop();
  54.         for (int u = 0; u <= 2; u ++) if (trie[pos].nxt[u]) {
  55.             int i = trie[pos].nxt[u];
  56.             int j = p[pos];
  57.  
  58.             while (j > 0 && trie[j].nxt[u] == 0)
  59.                 j = p[j];
  60.            
  61.             if (pos != 0 && trie[j].nxt[u]) j = trie[j].nxt[u];
  62.             p[i] = j;
  63.            
  64.             sum[i] += sum[j];
  65.             vi.push(i);
  66.         }
  67.     }
  68.  
  69.     // for (int i = 0; i < trie.size(); i ++) {
  70.     //     if (trie[i].nxt[0]) cout << i << ' ' << trie[i].nxt[0] << ' ' << 0 << 'n';
  71.     //     if (trie[i].nxt[1]) cout << i << ' ' << trie[i].nxt[1] << ' ' << 1 << 'n';
  72.     //     if (trie[i].nxt[2]) cout << i << ' ' << trie[i].nxt[2] << ' ' << 2 << 'n';
  73.     // }
  74.  
  75.     // for (int i = 0; i < trie.size(); i ++)
  76.     //     cout << "p[" << i << "]: " << p[i] << 'n';
  77.  
  78. }
  79.  
  80. ll count(const string &s, ll ans = 0) {
  81.     int pos = 0;
  82.     for (const char &ch: s) {
  83.         int u = ch - '0';
  84.         if (ch == '#') u = 2;
  85.         pos = trie[pos].nxt[u];
  86.         ans += sum[pos];
  87.     }
  88.     return ans;
  89. }
  90.  
  91. vector <string> save;
  92.  
  93. int main()
  94. {
  95.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  96.     #ifndef ONLINE_JUDGE
  97.         freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
  98.     #endif
  99.  
  100.     cin >> q;
  101.  
  102.     bool built = false;
  103.     for (int i = 1; i <= q; i ++) {
  104.         int op;
  105.         string s;
  106.         cin >> op >> s;    
  107.         if (op == 1) s = '#' + s;    
  108.         insert(s, op == 0);
  109.         if (op) save.push_back(s);
  110.     }
  111.  
  112.     build();
  113.  
  114.     for (const string &s: save) {
  115.         // cout << s << 'n';
  116.         cout << count(s) << 'n';
  117.     }
  118.  
  119.     return 0;
  120. }  
Parsed in 0.037 seconds