fork download
copy 
  1. #include <fstream>
  2. #include <cstdlib>
  3. #include <string>
  4. #define pb push_back
  5. using namespace std;
  6.  
  7. struct nodo
  8. {
  9.     bool fine,col;
  10.     nodo* figli[26];
  11.     nodo(){for(int i=0;i<26;i++) figli[i]=NULL; fine=false; col=false;}
  12. }root;
  13.  
  14. ifstream fin("input.txt");
  15. ofstream fout("output.txt");
  16.  
  17. int N;
  18. string S,maxS,sol;
  19.  
  20. void inserisci(nodo* N,string S,int P)
  21. {
  22.     if(P==S.size()) { N->fine=true; return; }
  23.  
  24.     if(N->figli[S[P]-'a']==NULL) N->figli[S[P]-'a']=new nodo;
  25.     inserisci(N->figli[S[P]-'a'],S,P+1);
  26. }
  27.  
  28. void colora(nodo* N,string S,int P)
  29. {
  30.     if(P==S.size()) return;
  31.     N->figli[S[P]-'a']->col=true;
  32.     colora(N->figli[S[P]-'a'],S,P+1);
  33. }
  34.  
  35. void dfsS(nodo *N)
  36. {
  37.     if(N->fine) sol.pb('P');
  38.     for(int i=0;i<26;i++)
  39.     {
  40.         if(N->figli[i]==NULL) continue;
  41.         sol.pb(char('a'+i));
  42.         dfsS(N->figli[i]);
  43.     }
  44.     sol.pb('-');
  45. }
  46.  
  47. void dfs(nodo *N,int conta)
  48. {
  49.     if(N->fine) sol.pb('P');
  50.     if(conta==maxS.size()) return;
  51.     int idx_col=-1;
  52.     for(int i=0;i<26;i++)
  53.     {
  54.         if(N->figli[i]==NULL) continue;
  55.         if(N->figli[i]->col) { idx_col=i; continue;}
  56.         sol.pb(char('a'+i));
  57.         dfsS(N->figli[i]);
  58.     }
  59.  
  60.     sol.pb(char('a'+idx_col));
  61.     dfs(N->figli[idx_col],conta+1);
  62. }
  63.  
  64. int main()
  65. {
  66.     fin>>N;
  67.     for(int i=0;i<N;i++)
  68.     {
  69.         fin>>S;
  70.         inserisci(&root,S,0);
  71.  
  72.         if(S.size()>maxS.size()) maxS=S;
  73.     }
  74.  
  75.     colora(&root,maxS,0);
  76.  
  77.     dfs(&root,0);
  78.  
  79.     fout<<sol.size()<<"\n";
  80.     for(int i=0;i<sol.size();i++) fout<<sol[i]<<"\n";
  81.  
  82.     return 0;
  83.  
  84. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/P6TMs3
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!