Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <string>
- #include <deque>
- #include <stdio.h>
- #include <stdlib.h>
- #define N (int)'z'-(int)'a'+1;
- #define A (int)'a';
- using namespace std;
- class Nodo{
- public:
- char c;
- int col;
- deque<class Nodo*> succ;
- };
- // lunghezza della stringa più lunga
- int max_lenght = 0;
- // lista dei caratteri da stampare su file
- deque<char> out;
- // 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)
- int search(class Nodo* n, int prof){
- if(prof == max_lenght){
- n->col = 2;
- return 2;
- }
- else{
- for(int i=0; i<n->succ.size(); i++)
- if(search(n->succ[i], prof+1) == 2){
- n->col = 2;
- return 2;
- }
- return 0;
- }
- }
- // visita di un nodo
- void visit(class Nodo* n){
- // stampo il carattere del nodo
- out.push_back(n->c);
- // se è un nodo foglio stampo P
- if(n->succ.size() == 0)
- out.push_back('P');
- // visito tutti i sottonodi
- for(int i=0; i<n->succ.size(); i++)
- visit(n->succ[i]);
- // stampo - per togliere il carattere
- out.push_back('-');
- }
- // visita per il ramo dell'albero in cui c'è la stringa da lasciare per ultima
- void visit2(class Nodo* n){
- out.push_back(n->c);
- if(n->succ.size() == 0)
- out.push_back('P');
- int i,index = -1;
- for(int i=0; i<n->succ.size(); i++)
- if(n->succ[i]->col == 2)
- index = i;
- else
- visit(n->succ[i]);
- if(n->col != 2)
- out.push_back('-');
- if(index != -1)
- visit2(n->succ[index]);
- }
- // costruzione dell'albero
- void insert(class Nodo* n, string s, int last_i){
- if(s.size() == last_i+1)
- return;
- if(n->succ.size() == 0){
- Nodo* e;
- e = new Nodo();
- last_i++;
- e->c = s[last_i];
- e->col = 0;
- n->succ.push_back(e);
- insert(n->succ[0], s, last_i);
- }
- else{
- last_i++;
- int flag = 0;
- int j;
- for(j=0; j<n->succ.size(); j++)
- if(n->succ[j]->c == s[last_i]){
- flag = 1;
- break;
- }
- if(flag)
- insert(n->succ[j], s, last_i);
- else{
- Nodo* e;
- e = new Nodo();
- e->c = s[last_i];
- e->col = 0;
- n->succ.push_back(e);
- insert(n->succ[n->succ.size()-1], s, last_i);
- }
- }
- }
- main(){
- FILE *pF = fopen("input.txt", "r");
- int n;
- fscanf(pF, "%d", &n);
- int i;
- char s2[21];
- string s;
- deque<class Nodo*> first;
- for(i=0; i<n; i++){
- fscanf(pF, "\n%s", s2);
- s = s2;
- if(s.size() > max_lenght)
- max_lenght = s.size();
- if(first.size() == 0){
- Nodo* n;
- n = new Nodo();
- n->c = s[0];
- n->col = 0;
- first.push_back(n);
- insert(first[0], s, 0);
- }
- else{
- int flag = 0;
- int j;
- for(j=0; j<first.size(); j++)
- if(first[j]->c == s[0]){
- flag = 1;
- break;
- }
- if(flag)
- insert(first[j], s, 0);
- else{
- Nodo* n;
- n = new Nodo();
- n->c = s[0];
- n->col = 0;
- first.push_back(n);
- insert(first[first.size()-1], s, 0);
- }
- }
- }
- fclose(pF);
- for(i=0; i<first.size(); i++)
- if(search(first[i], 1) == 2)
- break;
- int index = i;
- for(i=0; i<index; i++)
- visit(first[i]);
- for(i=index+1; i<first.size(); i++)
- visit(first[i]);
- visit2(first[index]);
- pF = fopen("output.txt", "w");
- fprintf(pF, "%d", out.size());
- for(i=0; i<out.size(); i++)
- fprintf(pF, "\n%c", out[i]);
- fclose(pF);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement