首页 > 代码库 > 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;
}