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

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;

}