#include #include #include #include #include #include using namespace std; /* Makro pro cyklus for */ #define REP(i, n) for (int i=0; inext[i]); delete t; } Trie* trie_create(char c, Trie *p) { Trie *t = new Trie; REP(i, 26) t->next[i] = NULL; t->end = false; t->val = 0; t->par = p; t->c = c; return t; } Trie* trie_find(Trie *t, char *s) { if (t==NULL) return NULL; while (*s!='\0') { char c = *s; if (t->next[c-'a']) { t = t->next[c-'a']; } else return 0; s++; } if (t->end) return t; return NULL; } Trie* trie_add(Trie *t, char *s, int val, Trie *b) { while(*s!='\0') { char c = *s; if (t->next[c-'a']==NULL) t->next[c-'a'] = trie_create(c, t); t = t->next[c-'a']; s++; } t->end = true; t->val = val; t->back = b; return t; } #define MAXN 1000 #define MAXL 1001 int n; Trie *trie; char words[MAXN][MAXL]; int len[MAXN]; int perm[MAXN]; char tmp[MAXL]; // Vlastní komparátor -- třídění permutace podle délky slov na daných indexech bool comp(const int &a, const int &b) { return (len[a]val > best) { best = t->val; back = t; } } // Přidej slovo do trie s nejlepší hodnotou žebříkus Trie *t = trie_add(trie, words[k], best+1, back); if (best+1 > ans) { ans = best + 1; node = t; } } // Získej výsledný žebřík vector res; while (node!=NULL) { // Postav reversi slova končící v aktuálním vrcholu string s; Trie *t = node; while (t->c!='\0') { s.push_back(t->c); t = t->par; } // Otoč jej a přidej do řešení res.push_back(string(s.rbegin(), s.rend())); // Pokračuj s předchůdcem žebříku node = node->back; } trie_free(trie); // Výpis řešení printf("%d\n", ans); for (int i=res.size()-1; i>=0; i--) printf("%s\n", res[i].c_str()); return 0; }