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