[Codeforces] F. String Set Queries

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : F. String Set Queries
Source            : Codeforces
Category          : String
Algorithm         : Aho Corasick Algorithm - Dynamic 
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
static const int maxn = 3e5 + 5;  
static const int logn = 20;  
  
struct AhoCorasick  
{  
      int sz, Num[maxn], backPoint[maxn];  
      map <char, int> Next[maxn];  
  
      void init()  
      {  
            assert(sz < maxn);  
            for (int i = 0; i <= sz; i++)  
            {  
                  Num[i] = 0;  
                  backPoint[i] = -1;  
                  Next[i].clear();  
            }  
            sz = 0;  
      }  
      AhoCorasick()  
      {  
            init();  
      }  
      void insertPattern(const string &pat)  
      {  
            int v = 0;  
            for (char ch : pat)  
            {  
                  if (Next[v].count(ch) == 0) Next[v][ch] = ++sz;  
                  v = Next[v][ch];  
            }  
            Num[v]++;  
      }  
      void findBackPointer() // Build Failure Function  
      {  
            queue <int> PQ;  
            PQ.emplace(0);  
            int v = 0;  
            while (!PQ.empty())  
            {  
                  int u = PQ.front(); PQ.pop();  
                  for (auto it : Next[u])  
                  {  
                        int v = it.second;  
                        char ch = it.first;  
                        int w = backPoint[u];  
                        while (w != -1 && Next[w].count(ch) == 0) w = backPoint[w];  
                        if (w == -1) backPoint[v] = 0;  
                        else backPoint[v] = Next[w][ch];  
                        Num[v] += Num[ backPoint[v] ];  
                        PQ.emplace(v);  
                  }  
            }  
      }  
      int insertTextAndQuery(const string &text)  
      {  
            int v = 0;  
            int ans = 0;  
            for (char ch : text)  
            {  
                  while (v != -1 && Next[v].count(ch) == 0) v = backPoint[v];  
                  if (v == -1) v = 0;  
                  else v = Next[v][ch];  
                  ans += Num[v];  
            }  
            return ans;  
      }  
};  
  
struct AhoCorasickDynamic  
{  
      vector <string> lst[logn];  
      AhoCorasick aho[logn];  
  
      void init()  
      {  
            for (int i = 0; i < logn; i++)  
            {  
                  lst[i].clear();  
                  aho[i].init();  
            }  
      }  
      AhoCorasickDynamic()  
      {  
            init();  
      }  
      void insertPattern(const string &pat)  
      {  
            int position = 0;  
            for (int i = 0; i < logn; i++)  
            {  
                  if (lst[i].empty())  
                  {  
                        position = i;  
                        break;  
                  }  
            }  
            lst[position].emplace_back(pat);  
            aho[position].insertPattern(pat);  
            for (int i = 0; i < position; i++)  
            {  
                  aho[i].init();  
                  for (string p : lst[i])  
                  {  
                        lst[position].emplace_back(p);  
                        aho[position].insertPattern(p);  
                  }  
                  lst[i].clear();  
            }  
            aho[position].findBackPointer();  
      }  
      int query(const string &text)  
      {  
            int ans = 0;  
            for (int i = 0; i < logn; i++) ans += aho[i].insertTextAndQuery(text);  
            return ans;  
      }  
};  
  
AhoCorasickDynamic add;  
AhoCorasickDynamic del;  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
      cout << fixed << setprecision(3);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n;  
      cin >> n;  
      int type;  
      string s;  
      for (int i = 0; i < n; i++)  
      {  
            cin >> type >> s;  
            if (type == 1) add.insertPattern(s);  
            else if (type == 2) del.insertPattern(s);  
            else cout << (add.query(s) - del.query(s)) << endl;  
      }  
  
}