题目描述

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

输入格式

第一行给出数字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树 f[]统计有该前缀的字符串数 容易发现可以用f[i]*i 来更新ans

#include<bits/stdc++.h>
using namespace std;
int a[5000][53],size=1,f[5000],ans;
string s;
int insert(){
    int now=0,len=s.length(),pos,i;
    for(i=0;i<len;++i){
        if(s[i]==' ')pos=52;
        else if(s[i]<='Z')pos=s[i]-'A';
        else pos=s[i]-'a'+26;
        if(a[now][pos])now=a[now][pos];
        else now=a[now][pos]=++size;
        f[now]++;
        ans=max(ans,f[now]*(i+1));
    }
}
int main(){
    freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int i,n;
    cin>>n;
    for(i=1;i<=n;++i){
        getline(cin,s);
        insert();
    }
    printf("%d",ans);
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *