https://vjudge.net/problem/UVA-11488
题意：
给定一个字符串集合S，定义P(s)为所有字符串的公共前缀长度与S中字符串个数的乘积。比如P( {000, 001, 0011} ) = 6。给n个01串，从中选择一个集合S，使得P(S)最大。
思路：
建立字典树，边插入边统计答案即可。
用两个变量分别记录前缀数量和前缀长度，每次插入时动态更新两者乘积。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = *+; int num;
int ans; struct Trie
{
int son[];
int cnt;
int id;
}t[maxn]; void init(int x)
{
t[x].cnt = t[x].id = ;
memset(t[x].son,,sizeof(t[x].son));
} void insert(char* s)
{
int u = , n = strlen(s);
for(int i=;i<n;i++)
{
int c = s[i]-'';
if(!t[u].son[c])
{
num++;
init(num);
t[u].son[c] = num;
}
int pre = u;
u = t[u].son[c];
t[u].id = t[pre].id+;
t[u].cnt++;
ans = max(t[u].cnt*t[u].id, ans);
}
} char s[]; int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
num = ans = ;
init();
int n; scanf("%d",&n);
while(n--)
{
scanf("%s",s);
insert(s);
}
printf("%d\n",ans);
}
return ;
}