LightOJ - DNA Prefix

#include<bits/stdc++.h>
using namespace std;
#define fastread() (ios_base::sync_with_stdio(false),cin.tie(NULL));

#define ll long long
ll ans, mx,cur,x,sz,last=1;
string s;

struct node{
    int next[4];
    ll cnt;
}r[2500109];

void trie(ll cur)
{
    r[cur].next[0]=-1;
    r[cur].next[1]=-1;
    r[cur].next[2]=-1;
    r[cur].next[3]=-1;
    r[cur].cnt=1;
}

int insert()
{
    sz=s.size();
    cur=0;
    for(int i =0;i<sz;i++)
    {
        if(s[i]=='A')x=0;
        else if(s[i]=='C')x=1;
        else if(s[i]=='G')x=2;
        else x=3;
        if(r[cur].next[x]==-1)
        {
            r[cur].next[x]=last;
            trie(last++);
            cur=r[cur].next[x];
        }
        else{
            cur=r[cur].next[x];
            r[cur].cnt++;
            mx= (i+1)*r[cur].cnt;
            ans=max(ans,mx);
        }
    }
    ans=max(ans,sz);
}
int main()
{
    fastread()
    ll test;
    cin>>test;
    for(int j=1;j<=test;j++)
    {
        ans=0,mx=0,last=1,sz=0;
        trie(0);
        ll n;
        cin>>n;
        while(n--)
        {
            cin>>s;
            insert();

        }
        cout<<"Case "<<j<<": "<<ans<<endl;
    }
}