题目描述
给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化.
输入
第一行给出数字N.N在[2,1000000] 下面N行描述这些字符串,长度不超过20000 。保证输入文件不超过10MB
输出
a single line with an integer representing the maximal level of complexity Lc(T).
样例输入
7
Jora de Sus
Orhei
Jora de Mijloc
Joreni
Jora de Jos
Japca
Orheiul Vechi
样例输出
24
题解
Trie树
很显然建立Trie树，用 每个节点的深度*对应字符串个数 更新答案。
但是本题卡空间，不能使用普通的Trie树存边方式，必须使用邻接表（链式前向星）存边。
所以每次插入时扫一遍，看能否扫到该字符，并决定是否添加新边。
时间复杂度$O(53len)$，卡卡常数可以过。另外数组大小已实测。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 5000010
using namespace std;
int tot = 1 , head[N] , to[N] , next[N] , cnt , si[N];
char val[N];
void add(int x , int y , char c)
{
to[++cnt] = y , val[cnt] = c , next[cnt] = head[x] , head[x] = cnt;
}
int main()
{
int n , i , j , k , t , p;
char ch;
long long ans = 0;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ )
{
ch = getchar();
while(ch == '
') ch = getchar();
for(j = t = 1 ; ch != '
' ; j ++ , ch = getchar())
{
for(p = 0 , k = head[t] ; k ; k = next[k])
{
if(val[k] == ch)
{
p = to[k];
break;
}
}
if(!p) add(t , p = ++tot , ch);
t = p , si[t] ++ , ans = max(ans , (long long)j * si[t]);
}
}
printf("%lld
" , ans);
return 0;
}