Pabon_SEC

Hyper Prefix Sets

Apr 4th, 2016
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. char s[50005][203];
  6.  
  7. int mx;
  8.  
  9. struct node
  10. {
  11.     bool endmark;
  12.  
  13.     int counter;
  14.  
  15.     node *next[4];
  16.  
  17.     node()
  18.     {
  19.         counter = 0;
  20.  
  21.         endmark = false;
  22.  
  23.         for(int i=0; i<2; i++)
  24.         {
  25.             next[i] = NULL;
  26.         }
  27.     }
  28.  
  29. }*root;
  30.  
  31.  
  32. void Insert(char *str,int len)
  33. {
  34.     node *curr = root;
  35.  
  36.     int child = 0;
  37.  
  38.     for(int i=0; i<len; i++)
  39.     {
  40.         int id = str[i] - '0';
  41.  
  42.         if(curr->next[id]==NULL)
  43.         {
  44.             curr->next[id] = new node();
  45.         }
  46.  
  47.         curr = curr->next[id];
  48.  
  49.         curr->counter++;
  50.  
  51.         child++;
  52.  
  53.         mx = max(mx,(child*curr->counter));
  54.     }
  55.  
  56.     curr->endmark = true;
  57. }
  58.  
  59. void del(node *curr)
  60. {
  61.     for(int i=0; i<2; i++)
  62.     {
  63.         if(curr->next[i])
  64.         {
  65.             del(curr->next[i]);
  66.         }
  67.     }
  68.  
  69.     delete(curr);
  70. }
  71.  
  72. int main()
  73. {
  74.     int num,i,a,test,len;
  75.  
  76.     scanf("%d",&test);
  77.  
  78.     while(test--)
  79.     {
  80.         root = new node();
  81.  
  82.         scanf("%d",&num);
  83.  
  84.         mx = 0;
  85.  
  86.         for(i=1; i<=num; i++)
  87.         {
  88.             scanf("%s",s[i]);
  89.  
  90.             len = strlen(s[i]);
  91.  
  92.             Insert(s[i],len);
  93.         }
  94.  
  95.         printf("%d\n",mx);
  96.  
  97.         del(root);
  98.     }
  99.  
  100.     return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment