SHARE
TWEET

LightOJ - DNA Prefix

jakaria_hossain May 8th, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fastread() (ios_base::sync_with_stdio(false),cin.tie(NULL));
  4.  
  5. #define ll long long
  6. ll ans, mx,cur,x,sz,last=1;
  7. string s;
  8.  
  9. struct node{
  10.     int next[4];
  11.     ll cnt;
  12. }r[2500109];
  13.  
  14. void trie(ll cur)
  15. {
  16.     r[cur].next[0]=-1;
  17.     r[cur].next[1]=-1;
  18.     r[cur].next[2]=-1;
  19.     r[cur].next[3]=-1;
  20.     r[cur].cnt=1;
  21. }
  22.  
  23. int insert()
  24. {
  25.     sz=s.size();
  26.     cur=0;
  27.     for(int i =0;i<sz;i++)
  28.     {
  29.         if(s[i]=='A')x=0;
  30.         else if(s[i]=='C')x=1;
  31.         else if(s[i]=='G')x=2;
  32.         else x=3;
  33.         if(r[cur].next[x]==-1)
  34.         {
  35.             r[cur].next[x]=last;
  36.             trie(last++);
  37.             cur=r[cur].next[x];
  38.         }
  39.         else{
  40.             cur=r[cur].next[x];
  41.             r[cur].cnt++;
  42.             mx= (i+1)*r[cur].cnt;
  43.             ans=max(ans,mx);
  44.         }
  45.     }
  46.     ans=max(ans,sz);
  47. }
  48. int main()
  49. {
  50.     fastread()
  51.     ll test;
  52.     cin>>test;
  53.     for(int j=1;j<=test;j++)
  54.     {
  55.         ans=0,mx=0,last=1,sz=0;
  56.         trie(0);
  57.         ll n;
  58.         cin>>n;
  59.         while(n--)
  60.         {
  61.             cin>>s;
  62.             insert();
  63.  
  64.         }
  65.         cout<<"Case "<<j<<": "<<ans<<endl;
  66.     }
  67. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top