[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
 
***********************************************/