Solution of UVa 11488-Hyper Prefix Sets

See the problem UVa-11488

 

>>>This problem has been solved using "Trie". So if you don't known with "Trie", you should not try to understand this solution.<<<

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll cur, last, ss, sss, ans, mx;
string s;

struct node{
    int next[2];
    long long cnt;
}ar[10000009];

void new_trie(int cur){
    ar[cur].next[0]=-1;
    ar[cur].next[1]=-1;
    ar[cur].cnt=1;
}

int insrt(){
    ss=s.size(), cur=0;
    for(int k=0; k<ss; k++){
        int x=(int)s[k]-48;
        if(ar[cur].next[x]==-1){
            ar[cur].next[x]=last;
            new_trie(last++);
            cur=ar[cur].next[x];
        }
        else{
            cur=ar[cur].next[x];
            ar[cur].cnt++;
            mx=(k+1)*ar[cur].cnt;
            ans=max(mx, ans);
        }
    }
    sss=max(ss, sss);
}

int main(){
    long long t, n;
    cin>>t;
    while(t--){
        ans=0, mx=0, last=1, sss=0;
        new_trie(0);
        cin>>n;
        while(n--){
            cin>>s;
            insrt();
        }
        cout<<max(ans, sss)<<endl;
    }
    return 0;
}