jakaria_hossain

LightOJ - DNA Prefix

May 8th, 2019
82
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