[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;  
      }  
  
}  

[Codeforces] D. Frequency of String

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : D. Frequency of String
Source            : Codeforces
Category          : Data Structure, String
Algorithm         : Aho Corasick Algorithm
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
#define memo(a, b)                      memset(a, b, sizeof a)  
  
static const int maxn = 5e5 + 5;  
  
int Next[27][maxn], End[maxn], sz, Num[maxn], backPoint[maxn];  
bool created[maxn];  
vector <int> out[maxn], patternIndices[maxn], occur[maxn];  
  
string text, pattern[maxn];  
int numPat, k[maxn];  
  
  
void init()  
{  
      sz = 0;  
      memo(Next, 0);  
      memo(created, 0);  
      memo(Num, 0);  
      for (int i = 0; i < maxn; i++)  
      {  
            out[i].clear();  
            patternIndices[i].clear();  
      }  
}  
  
void insertPattern(const string &pat, const int id)  
{  
      int v = 0;  
      for (char ch : pat)  
      {  
            int val = ch - 'a';  
            if (!created[ Next[val][v] ])  
            {  
                  ++sz;  
                  Next[val][v] = sz;  
                  created[sz] = 1;  
            }  
            v = Next[val][v];  
      }  
      patternIndices[v].emplace_back(id);  
}  
  
void findBackPointer() // Build Failure Function  
{  
      queue <int> PQ;  
      int v = 0;  
      for (int i = 0; i < 26; i++)  
      {  
            if (Next[i][v])  
            {  
                  PQ.emplace(Next[i][v]);  
                  backPoint[ Next[i][v] ] = v;  
                  out[v].emplace_back(Next[i][v]);  
            }  
      }  
      while (!PQ.empty())  
      {  
            int u = PQ.front(); PQ.pop();  
            for (int i = 0; i < 26; i++)  
            {  
                  int v = Next[i][u];  
                  if (!v) continue;  
                  int w = backPoint[u];  
                  while (w && Next[i][w] == 0) w = backPoint[w];  
                  backPoint[v] = Next[i][w];  
                  out[ Next[i][w] ].push_back(v);  
                  for (int p : patternIndices[ Next[i][w] ]) patternIndices[v].push_back(p);  
                  PQ.emplace(v);  
            }  
      }  
}  
  
void insertText(const string &text)  
{  
      int v = 0;  
      for (int i = 0; i < text.size(); i++)  
      {  
            int val = text[i] - 'a';  
            while (v && Next[val][v] == 0) v = backPoint[v];  
            v = Next[val][v];  
            for (int p : patternIndices[v]) occur[p].push_back(i);  
      }  
}  
  
int query(int id)  
{  
      int len = pattern[id].size();  
      int occ = occur[id].size();  
      if (occ < k[id]) return -1;  
      int mini = 1e7;  
      for (int i = 0, j = k[id] - 1; j < occ; i++, j++) mini = min(mini, occur[id][j] - occur[id][i]);  
      return mini + len;  
}  
  
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  
  
      init();  
  
      cin >> text >> numPat;  
      for (int i = 1; i <= numPat; i++)  
      {  
            cin >> k[i] >> pattern[i];  
            insertPattern(pattern[i], i);  
      }  
      findBackPointer();  
      insertText(text);  
      for (int i = 1; i <= numPat; i++) cout << query(i) << '\n';  
}