See the problem 1224 - DNA Prefix
/*
Bismillahir Rahmanir Rahim
Solution using "Trie"
*/
#include<bits/stdc++.h>
using namespace std;
long long k, i=0, x, cur, last, ss, sss, ans, mx;
string s;
struct node{
int next[4];
long long cnt;
}ar[2500109];
void new_trie(int cur){
ar[cur].next[0]=-1;
ar[cur].next[1]=-1;
ar[cur].next[2]=-1;
ar[cur].next[3]=-1;
ar[cur].cnt=1;
}
int insrt(){
ss=s.size(), cur=0;
for(k=0; k<ss; k++){
if(s[k]=='A') x=0;
else if(s[k]=='C')x=1;
else if(s[k]=='G')x=2;
else if(s[k]=='T')x=3;
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, cs=1;
cin>>t;
while(t--){
ans=0, mx=0, last=1, sss=0;
new_trie(0);
cin>>n;
while(n--){
cin>>s;
i++;
insrt();
}
cout<<"Case "<<cs++<<": "<<max(ans, sss)<<endl;
}
return 0;
}
|
This comment has been removed by a blog administrator.
ReplyDelete