HDU 11488 Hyper Prefix Sets （字符串-Trie树）

yanchuen

　　

H	Hyper Prefix Sets

　　 　　 　　Prefix goodness of a set string is length of longest common prefix*number of strings in the set. For example the prefix goodness of the set {000,001,0011} is 6.You are given a set of binary strings. Find the maximum prefix goodness 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 with n(≤50000) the number of strings. Each of the next n lines contains a string containing only 0 and 1. Maximum length of each of these string is 200. 　　Output For each test case output the maximum prefix goodness among all possible subsets of n binary strings. Sample Input Output for Sample Input

4 　　4 　　0000 　　0001 　　10101 　　010 　　2 　　01010010101010101010 　　11010010101010101010 　　3 　　010101010101000010001010 　　010101010101000010001000 　　010101010101000010001010 　　5 　　01010101010100001010010010100101 　　01010101010100001010011010101010 　　00001010101010110101 　　0001010101011010101 　　00010101010101001

6 　　20 　　66 　　44

　　Problem Setter : Abdullah Al Mahmud Special Thanks : Manzurur Rahman Khan 　　题目大意： 　　

　　如果a表示公共前缀的长度，b表示含有这个前缀的字符串个数，问你a*b的最大值。

　　 　　解题思路： 　　

　　建立一棵Trie树，边建边查，直接更新 长度乘以个数的最大值

　　 　　解题代码： 　　#include #include #include #include using namespace std; const int maxn=500000; int tree[maxn][2]; int val[maxn],cnt; int n,ans; void insert(string st){ int s=0; for(int i=0;ians) ans=(i+1)*val; } } void initial(){ cnt=ans=0; memset(val,0,sizeof(val)); memset(tree,0,sizeof(tree)); } void solve(){ cin>>n; for(int i=0;i>st; insert(st); } cout SO娱乐城：真_人.足球.彩票齐全| 开户送10元.首存送58元.手机可投μ注任何游戏顶级信用μ提现即时到账SO.CC