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

[CodeChef] Music & Lyrics

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Music & Lyrics
Source            : CodeChef
Category          : String
Algorithm         : Aho-Corasick Algorithm
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
const int mxPat = 5000 + 5;
const int mxText = 50000 + 5;
 
struct node
{
      int cnt;
      bool vis;
      node* next[200];
      vector <node *> bpin;
      node()
      {
            cnt = 0;
            vis = false;
            for (int i = 0; i < 200; i++) next[i] = NULL;
            bpin.clear();
    }
    ~node()
    {
          for (int i = 1; i < 200; i++)
          {
                if (next[i] && next[i] != this) delete next[i];
          }
    }
}*root;
 
inline void buildTrie(char dictionary[][mxPat], int n)
{
      // dictionary[][] = all query word
      // n              = total query word
      root = new node();
      // usual trie tree
      for (int i = 0; i < n; i++)
      {
            node* curr = root;
            for (int j = 0; dictionary[i][j]; j++)
            {
                  int val = dictionary[i][j] - '0' + 10;
                  if (curr->next[val] == NULL) curr->next[val] = new node();
                  curr = curr->next[val];
            }
      }
      // Pushing adjacent node to root into queue
      queue <node *> PQ;
      for (int i = 0; i < 200; i++)
      {
            if (root->next[i] == NULL)
            {
                  root->next[i] = root;
            }
            else
            {
                  PQ.push(root->next[i]);
                  root->next[i]->next[0] = root;  // ->next[0] = back pointer
            }
      }
      //Building Aho - Corasik tree
      while (!PQ.empty())
      {
            node* u = PQ.front();   // parent node
            PQ.pop();
            for (int i = 1; i < 200; i++)
            {
                  if (u->next[i])
                  {
                        node* v = u->next[i];   // child node
                        node* w = u->next[0];   // back pointer of parent node
                        while (!w->next[i])     // untill the char (i - 'a' + 1) child is not found
                              w = w->next[0];
                        v->next[0] = w = w->next[i];  // back pointer of v will be found child above
                        w->bpin.push_back(v);    // bpin will be used in dfs
                                                // here w is the new found match node
                        PQ.push(v);
                  }
            }
      }
}
 
// Third step processing the text
void aho_corasik(char word[][mxText], int n)
{
      //node* p = root;
      for (int i=0; i<n; i++)
      {
            node* p = root;
            for (int j = 0; word[i][j]; j++)
            {
                  //if (word[i][j] == '-')
                  //    continue;
 
                  int id = word[i][j] - '0' + 10;
                  while (!p->next[id])
                        p = p->next[0];
                  p = p->next[id];
                  p->cnt++;
            }
      }
}
 
// DFS for counting
int dfs(node* p)
{
      if (p->vis) return p->cnt;
      p->vis = true;
      for (int i = 0; i < (int)p->bpin.size(); i++)
            p->cnt += dfs(p->bpin[i]);
      return p->cnt;
}
 
char word[105][mxText];
char dictionary[505][mxPat];
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      int pat;
      scanf("%d", &pat);
      for (int i = 0; i < pat; i++)
            scanf("%s", dictionary[i]);
      buildTrie(dictionary, pat);
      int text;
      scanf("%d", &text);
      for (int t = 0; t < text; t++)
            scanf("%s", word[t]);
      aho_corasik(word, text);
      for (int i = 0; i < pat; i++)
      {
            node* p = root;
            for (int j = 0; dictionary[i][j]; j++)
            {
                  int id = dictionary[i][j] - '0' + 10;
                  if (p->next[id]) p = p->next[id];
            }
            printf("%d\n", dfs(p));
      }
      delete root;
      return 0;
}
 
 
 
/*************************************************
>>>>>> Input - 1
 
5
he
she
sher
his
hers
2
ushers
she-said-he-said-she-said-he-said-his
 
>>>>>> Output - 1
5
3
1
1
1
 
>>>>>> Input - 2
 
3
who
shawty
hawt
2
Get-it-shawty-Get-it-shawty
Whoa-W-W-Whoa-Shawtyyyyy
 
>>>>> Output - 2
 
0
2
3
 
***********************************************/