BZOJ 1174 [Balkan2007]Toponyms(Trie)

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1174

【题目大意】

  选出一些字符串,使得字符串的最长公共前缀*字符串的总个数最大化

【题解】

  字典树裸题,卡内存,需要用链表实现

【代码】

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int S=5000100;
struct Trie{
int tot,cnt[S],ans,head[S],nxt[S],to[S],m;
char c[S];
void insert(){
char C=getchar();
for(int x=0,i=0;C!='\n';i++,C=getchar()){
int y=-1;
for(int e=head[x];e;e=nxt[e])if(c[e]==C){y=to[e];break;}
if(y<0)to[++m]=++tot,c[m]=C,nxt[m]=head[x],head[x]=m,y=tot;
cnt[x=y]++;
ans=max(ans,cnt[x]*(i+1));
}
}
}T;
int n;
int main(){
scanf("%d",&n); getchar();
for(int i=1;i<=n;i++)T.insert();
printf("%d\n",T.ans);
return 0;
}
上一篇:zabbix实时监控oracle数据变化


下一篇:8021x 获取IP信息失败,请检查锐捷认证客户端当前配置是否符合所在网络的要求,检查完毕后尝试重新认证