Advertisement
Guest User

printer.cpp

a guest
Aug 20th, 2014
191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.27 KB | None | 0 0
  1. #include <string>
  2. #include <deque>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. #define N (int)'z'-(int)'a'+1;
  7. #define A (int)'a';
  8.  
  9. using namespace std;
  10.  
  11. class Nodo{
  12.     public:
  13.         char c;
  14.         int col;
  15.         deque<class Nodo*> succ;
  16. };
  17.  
  18. // lunghezza della stringa più lunga
  19. int max_lenght = 0;
  20.  
  21. // lista dei caratteri da stampare su file
  22. deque<char> out;
  23.  
  24.  
  25. // funzione che cerca una stringa con lunghezza max_lenght e setta i colori a 2 (la stringa formata da quei caratteri sarà l'ultima da stampare)
  26. int search(class Nodo* n, int prof){
  27.    
  28.     if(prof == max_lenght){
  29.         n->col = 2;
  30.         return 2;
  31.     }
  32.     else{
  33.         for(int i=0; i<n->succ.size(); i++)
  34.             if(search(n->succ[i], prof+1) == 2){
  35.                 n->col = 2;
  36.                 return 2;
  37.             }
  38.        
  39.         return 0;
  40.     }
  41. }
  42.  
  43. // visita di un nodo
  44. void visit(class Nodo* n){
  45.     // stampo il carattere del nodo
  46.     out.push_back(n->c);
  47.     // se è un nodo foglio stampo P
  48.     if(n->succ.size() == 0)
  49.         out.push_back('P');
  50.     // visito tutti i sottonodi
  51.     for(int i=0; i<n->succ.size(); i++)
  52.         visit(n->succ[i]);
  53.     // stampo - per togliere il carattere
  54.     out.push_back('-');
  55. }
  56.  
  57. // visita per il ramo dell'albero in cui c'è la stringa da lasciare per ultima
  58. void visit2(class Nodo* n){
  59.    
  60.     out.push_back(n->c);
  61.     if(n->succ.size() == 0)
  62.         out.push_back('P');
  63.  
  64.     int i,index = -1;
  65.     for(int i=0; i<n->succ.size(); i++)
  66.         if(n->succ[i]->col == 2)
  67.             index = i;
  68.         else
  69.             visit(n->succ[i]);
  70.    
  71.     if(n->col != 2)
  72.         out.push_back('-');
  73.    
  74.     if(index != -1)
  75.         visit2(n->succ[index]);
  76. }
  77.  
  78. // costruzione dell'albero
  79. void insert(class Nodo* n, string s, int last_i){
  80.    
  81.     if(s.size() == last_i+1)
  82.         return;
  83.    
  84.     if(n->succ.size() == 0){
  85.         Nodo* e;
  86.         e = new Nodo();
  87.         last_i++;
  88.         e->c = s[last_i];
  89.         e->col = 0;
  90.         n->succ.push_back(e);
  91.         insert(n->succ[0], s, last_i);
  92.     }
  93.     else{
  94.         last_i++;
  95.         int flag = 0;
  96.         int j;
  97.         for(j=0; j<n->succ.size(); j++)
  98.             if(n->succ[j]->c == s[last_i]){
  99.                 flag = 1;
  100.                 break;
  101.             }
  102.         if(flag)
  103.             insert(n->succ[j], s, last_i);
  104.         else{
  105.             Nodo* e;
  106.             e = new Nodo();
  107.             e->c = s[last_i];
  108.             e->col = 0;
  109.             n->succ.push_back(e);
  110.             insert(n->succ[n->succ.size()-1], s, last_i);
  111.         }
  112.     }
  113.    
  114. }
  115.  
  116. main(){
  117.     FILE *pF = fopen("input.txt", "r");
  118.     int n;
  119.     fscanf(pF, "%d", &n);
  120.     int i;
  121.     char s2[21];
  122.     string s;
  123.     deque<class Nodo*> first;
  124.    
  125.     for(i=0; i<n; i++){
  126.         fscanf(pF, "\n%s", s2);
  127.         s = s2;
  128.         if(s.size() > max_lenght)
  129.             max_lenght = s.size();
  130.            
  131.         if(first.size() == 0){
  132.             Nodo* n;
  133.             n = new Nodo();
  134.             n->c = s[0];
  135.             n->col = 0;
  136.             first.push_back(n);
  137.             insert(first[0], s, 0);
  138.         }
  139.         else{
  140.             int flag = 0;
  141.             int j;
  142.             for(j=0; j<first.size(); j++)
  143.                 if(first[j]->c == s[0]){
  144.                     flag = 1;
  145.                     break;
  146.                 }
  147.             if(flag)
  148.                 insert(first[j], s, 0);
  149.             else{
  150.                 Nodo* n;
  151.                 n = new Nodo();
  152.                 n->c = s[0];
  153.                 n->col = 0;
  154.                 first.push_back(n);
  155.                 insert(first[first.size()-1], s, 0);
  156.             }
  157.         }
  158.     }
  159.     fclose(pF);
  160.  
  161.     for(i=0; i<first.size(); i++)
  162.         if(search(first[i], 1) == 2)
  163.             break;
  164.    
  165.     int index = i;
  166.    
  167.     for(i=0; i<index; i++)
  168.         visit(first[i]);
  169.  
  170.     for(i=index+1; i<first.size(); i++)
  171.         visit(first[i]);
  172.        
  173.     visit2(first[index]);
  174.    
  175.     pF = fopen("output.txt", "w");
  176.     fprintf(pF, "%d", out.size());
  177.     for(i=0; i<out.size(); i++)
  178.         fprintf(pF, "\n%c", out[i]);
  179.     fclose(pF);
  180. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement