UVA 11488 Hyper Prefix Sets (Trie) - c++编程基础

TOP

UVA 11488 Hyper Prefix Sets (Trie)

2015-07-20 17:33:20 来源: 作者: 【大中小】浏览:2次

Hyper Prefix Sets

Prefix goodness of a set string islength of longest common prefix*number of strings in the set.For example the prefix goodness of theset {000,001,0011} is 6.You are given a set of binarystrings. Find the maximum prefixgoodness among all possible subsets of these binary strings.

Input

First line of the input contains T(≤20)the number of test cases. Each of the test cases start withn(≤50000) the number of strings. Eachof the next n lines contains a string containing only 0 andMaximum length of each of thesestring is 200.

Output

For each test case output the maximumprefix goodness among all possible subsets of n binarystrings.

Sample Input

0000

0001

10101

010

01010010101010101010

11010010101010101010

010101010101000010001010

010101010101000010001000

010101010101000010001010

01010101010100001010010010100101

01010101010100001010011010101010

00001010101010110101

0001010101011010101

00010101010101001

Output for Sample Input

Problem Setter : Abdullah Al Mahmud

Special Thanks : Manzurur Rahman Khan

题意：
给出N个字符串，要求选出若干个，使得选中的字符串的公共前缀长度与选中字符串的个数的乘积最大。
分析：
简单粗暴的Trie模板题。
对于Tire中的每一个结点添加两个信息：该结点的深度及该结点杯访问的次数，最后求出这两个信息的最大值就行了，边加入字符串边维护就行。

/*
 *
 * Author : fcbruce
 *
 * Time : Sat 04 Oct 2014 09:17:50 PM CST
 *
 */
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include
                 #include 
                 
                   #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #ifdef _WIN32 #define lld %I64d #else #define lld %lld #endif #define maxm 2 #define maxn 5000007 using namespace std; struct Trie { int ch[maxn][maxm]; int deep[maxn]; int cnt[maxn][maxm]; int MAX; int sz; Trie() { sz=1; deep[0]=0; MAX=0; memset(cnt[0],0,sizeof cnt[0]); memset(ch[0],0,sizeof ch[0]); } void clear() { sz=1; deep[0]=0; MAX=0; memset(cnt[0],0,sizeof cnt[0]); memset(ch[0],0,sizeof ch[0]); } int idx(const char ch) { return ch-'0'; } void insert(const char *s) { for (int i=0,j=0;s[i]!='';i++) { int c=idx(s[i]); if (ch[j][c]==0) { memset(ch[sz],0,sizeof ch[sz]); memset(cnt[sz],0,sizeof cnt[sz]); deep[sz]=i+1; ch[j][c]=sz++; } j=ch[j][c]; cnt[j][c]++; MAX=max(MAX,deep[j]*cnt[j][c]); } } }trie; char str[233]; int main() { #ifdef FCBRUCE freopen(/home/fcbruce/code/t,r,stdin); #endif // FCBRUCE int T_T; scanf(%d,&T_T); while (T_T--) { trie.clear(); int n; scanf(%d,&n); for (int i=0;i
                  
                   ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：BNUOJ34973Liserious战队	下一篇：C++中使用Json的方法

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: