UVA - 11488 Hyper Prefix Sets 【trie树】

题目大意：给你若干个01串，让你求出 前缀长度*有该前缀的字符串个数 的最大值

裸题

#include <bits/stdc++.h>
using namespace std;
const int maxn=500000+50;
typedef long long ll;
struct node
{
    int next[27];
    int v,num;
    void init()
    {
        v=0;
        num=0;
        memset(next,-1,sizeof(next));
    }
};
node l[maxn];
int tot=0;
ll ans=0;
void add(char a[],int len)
{
    int now=0;

    for(int i=0;i<len;i++)
    {
        int tmp=a[i]-'0';
        int next=l[now].next[tmp];
        if(next==-1)
        {
            next=++tot;
            l[next].init();
            l[now].next[tmp]=next;
            l[next].num=l[now].num+1;
        }
        now=next;
        l[now].v++;
        ans=max(ans,(ll)(l[now].v*l[now].num));
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ans=0;
        int n;
        char a[maxn];
        scanf("%d",&n);
        l[0].init();
        for(int i=1;i<=n;i++)
        {
            scanf("%s",a);
            int len=strlen(a);
            add(a,len);
        }
        printf("%lld\n",ans);
    }
    return 0;
}