[toph.co] Treat Hunter

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Treat Hunter
Source            : toph.co
Category          : String
Algorithm         : Trie
Verdict           : Accepted

// Note : Trie using Linked List gives TLE

#include <bits/stdc++.h>
 
using namespace std;
 
static const int MAXN = 500500;
 
int Next[27][MAXN];
int End[MAXN];
bool created[MAXN];
int sz;
 
inline void INSERT(string &s)
{
      sort(s.begin(), s.end());
      int v = 0;
      for (char ch : s)
      {
            int val = ch - 'a';
            if (!created[Next[val][v]])
            {
                  sz++;
                  Next[val][v] = sz;
                  created[sz] = 1;
            }
            v = Next[val][v];
      }
      End[v]++;
}
 
inline int FIND_STRING(string &s)
{
      sort(s.begin(), s.end());
      int v  = 0;
      for (char ch : s)
      {
            int val = ch - 'a';
            if (!created[Next[val][v]]) return 0;
            v = Next[val][v];
      }
      return End[v];
}
 
int main()
{
//      freopen("in.txt", "r", stdin);
 
      int tc;
      scanf("%d", &tc);
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            int n, q;
            scanf("%d %d", &n, &q);
            char s[14];
            sz = 0;
            memset(created, 0, sizeof(created));
            memset(Next, 0, sizeof(Next));
            memset(End, 0, sizeof(End));
            for (int i = 0; i < n; i++)
            {
                  scanf("%s", s);
                  string str(s);
                  INSERT(str);
            }
            printf("Case %d:\n", tcase);
            while (q--)
            {
                  scanf("%s", s);
                  string str(s);
                  printf("%d\n", n - FIND_STRING(str));
            }
      }
}