Marcadian’s Blog

Another trie soal pertama di OJ yg AC pake trie, ini ga pake pointer2an cuma pake array 

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MA 5000010
using namespace std;
typedef struct Tnode
{
 int counter;
 char p;
 int child[3];
}node;

char s[210];
node trie[MA];
int idx,len;
int res;

void insert(int trid,int id)
{
 trie[trid].counter++;
 if (id == len) return;
 if (trie[trid].child[s[id]-'0']==-1)
 {
  idx++;
  trie[idx].p = s[id];
  trie[trid].child[s[id]-'0'] = idx;
 }
 insert(trie[trid].child[s[id]-'0'], id+1);
}

void calc(int idx,int length)
{
 res = max(res, trie[idx].counter * length);
 if (trie[idx].child[0]!=-1) calc(trie[idx].child[0],length+1);
 if (trie[idx].child[1]!=-1) calc(trie[idx].child[1],length+1);
}

int main()
{
 int  t,n;
 scanf("%d",&t);
 while (t--)
 {
  idx = 0;
  scanf("%d",&n);
  for(int i=0;i<MA;i++)
   trie[i].counter = 0,trie[i].child[0] = trie[i].child[1] =-1;

  while (n--)
  {
   scanf("%s",s);
   len = strlen(s);
   insert(0,0);
  }
  res = 0;
  calc(0,0);
  printf("%d\n",res);
 }
 return 0;
}