首页 > 代码库 > HDU 11488 Hyper Prefix Sets (字符串-Trie树)
HDU 11488 Hyper Prefix Sets (字符串-Trie树)
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 <iostream> #include <cstring> #include <string> #include <cstdio> 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;i<st.length();i++){ if( tree[s][st[i]-'0']==0 ) tree[s][st[i]-'0']=++cnt; s=tree[s][st[i]-'0']; val[s]++; if((i+1)*val[s]>ans) ans=(i+1)*val[s]; } } void initial(){ cnt=ans=0; memset(val,0,sizeof(val)); memset(tree,0,sizeof(tree)); } void solve(){ cin>>n; for(int i=0;i<n;i++){ string st; cin>>st; insert(st); } cout<<ans<<endl; } int main(){ int t; cin>>t; while(t-- >0){ initial(); solve(); } return 0; }