首页 > 代码库 > UVa11488-Hyper Prefix Sets(trie树)
UVa11488-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
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <string> #include <algorithm> #include <queue> using namespace std; const int maxn = 5000000; vector<string> vs; int cnt,ans,n; int ch[maxn][2]; int val[maxn]; inline int getIdx(char a){ return a-'0'; } void insert(string st){ int u = 0; for(int i = 0; i < st.size(); i++){ int k = getIdx(st[i]); if(!ch[u][k]){ memset(ch[cnt],0,sizeof ch[cnt]); val[cnt]++; ans = max(ans,val[cnt]*(i+1)); ch[u][k] = cnt++; }else{ val[ch[u][k]]++; ans = max(ans,val[ch[u][k]]*(i+1)); } u = ch[u][k]; } } int main(){ int ncase; cin >> ncase; while(ncase--){ vs.clear(); memset(val,0,sizeof val); memset(ch[0],0,sizeof ch[0]); cnt = 1; ans = 0; cin >> n; while(n--){ string st; cin >> st; insert(st); } cout<<ans<<endl; } return 0; }