「BZOJ1174」[Balkan2007] Toponyms

2014年4月2日4,5464

Description

给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化.

Input

第一行给出数字N.N在[2,1000000] 下面N行描述这些字符串,长度不超过20000 总输入不超过20000字符

Output

a single line with an integer representing the maximal level of complexity Lc(T).

Sample Input

7
Jora de Sus
Orhei
Jora de Mijloc
Joreni
Jora de Jos
Japca
Orheiul Vechi

Sample Output

题解

首先写了个re不断的字典树

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,sz=1,ans;
string ch;
int a[500001][53],f[500001];
void insert()
{
	int l=ch.length(),now=0;
	for(int i=0;i<l;i++)
	{
		int t;
		if(ch[i]==' ')t=52;
		else if(ch[i]<='Z')t=ch[i]-'A';
        else t=ch[i]-'a'+26;
		if(a[now][t])now=a[now][t];
		else now=a[now][t]=++sz;
		f[now]++;
		ans=max(ans,f[now]*(i+1));
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
	   getline(cin,ch);
	   insert();
    }
    printf("%d",ans);
	return 0;
}