fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. map<char,int>mark;
  4. struct node{
  5.     int cnt_trees;
  6.     bool end_mark;
  7.     node *next[4];
  8.     node(){
  9.         cnt_trees=0;
  10.         end_mark=false;
  11.         for(int i=0;i<4;i++) next[i]=NULL;
  12.     }
  13. }*root;
  14.  
  15. void insert_into_Trie(string str,map<char,int> mark){
  16.     node *cur=root;
  17.     for(int i=0;str[i];i++){
  18.         char ch=str[i];
  19.         int id=mark[ch];
  20.         if(cur->next[id]==NULL)
  21.             cur->next[id]=new node();
  22.             cur=cur->next[id];
  23.             cur->cnt_trees++;
  24.     }
  25. }
  26.  
  27. int search_into_Trie(string str,map<char,int> mark){
  28.     node *cur=root;
  29.     int mx=-1;
  30.     for(int i=0;str[i];i++){
  31.         char ch=str[i];
  32.         int id=mark[ch];
  33.  
  34.         cur=cur->next[id];
  35.         int koita_ache=cur->cnt_trees;
  36.         int len=i+1;
  37.         int lo_max=koita_ache*len;
  38.         //cout<<lo_max<<endl;
  39.         if(mx<lo_max) mx=lo_max;
  40.     }
  41.     return mx;
  42. }
  43.  
  44.  
  45. void del(node* cur)
  46. {
  47.     for(int i= 0;i<4;i++)
  48.         if (cur->next[i])
  49.             del(cur->next[i]);
  50.  
  51.     delete(cur);
  52. }
  53.  
  54. int main()
  55. {
  56.     mark['A']=0;mark['C']=1;mark['G']=2;mark['T']=3;
  57.     int tc,n,q,cs=0;
  58.     string str;
  59.         cin>>tc;
  60.         while(tc--){
  61.         root=new node();
  62.         cin>>n;
  63.         vector<string>v;
  64.         while(n--){
  65.             cin>>str;
  66.             insert_into_Trie(str,mark);
  67.             v.push_back(str);
  68.         }
  69.         int local_max=-1;
  70.         for(int i=0;i<v.size();i++){
  71.             int ck_max=search_into_Trie(v[i],mark);
  72.             if(ck_max>local_max) local_max=ck_max;
  73.         }
  74.         cout<<"Case "<<++cs<<": ";
  75.         cout<<local_max<<endl;
  76.         del(root);
  77.         }
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
3
4
ACGT
ACGTGCGT
ACCGTGC
ACGCCGT
3
CGCGCGCGCGCGCCCCGCCCGCGC
CGCGCGCGCGCGCCCCGCCCGCAC
CGCGCGCGCGCGCCCCGCCCGCTC
2
CGCGCCGCGCGCGCGCGCGC
GGCGCCGCGCGCGCGCGCTC
stdout
copy 
Case 1: 9
Case 2: 66
Case 3: 20
https://ideone.com/5J1KcD
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!