/*
ЗАДАЧА А3. ДУМОРЕДИЦА

Да наречем "думоредица" такава редица от думи, в която първата дума има три
букви, а всяка следваща се образува от предната с добавяне на една буква и
евентуално разместваване на буквите. Напишете програма WORCH.EXE, която по
зададено множество от думи - речник - намира една най-дълга думоредица, която
може да бъде образувана от думи на речника.

Входните данни, т.е. речникът, се чете от стандартния вход и съдържа не повече
от 250 000 думи. Всяка дума е записана на отделен ред и съдържа само малки
латински букви.

Резултатът трябва да се изведе на стандартния изход и да съдържа намерената
думоредица – всяка дума на отделен ред.


ПРИМЕР

Вход:

ala
bala
crate
racket
tar
tear
labat
 

Изход:

tar
tear
crate
racket



Решение на задача А3 - Думоредица
От Иван Анев

Добър подход при решаването на задачи е първо да се измисли подход (алгоритъм)
за решаването на конкретната задача без да се обвързваме с реализация, а едва
след съставянето на алгоритъма да изчислим неговата сложност и да помислим как
може да се реализират отделните части задоволително бързо.

За поставената задача трябва да изчислим за всяка дума дължината на най-дългата
редица от описания вид, на която думата може да е край. Това лесно може да стане
като изчисляваме тази стойност за думите в нарастващ ред на тяхната дължина,
като за всяка дума проверяваме от кой думи може да се получи и взимаме тази от
тях с най-голяма стойност на функцията, която изчисляваме. Така за думата, която
в момента разглеждаме резултата ще е с единица по-голям.

След като сме представили подхода, по който ще работим, ще представим и
конкретната реализация. По условие при получаване на нова дума можем да
размесваме произволно буквите на изходната думата. Това означава, че всяка дума
е еквивалента на дума след като приложим произволно разместване на буквите.
Това ни позволява за всяка дума да вземем нейното разместване, което е
минимално лексикографски от всички възможни.

Когато търсим за някоя дума A с дължина x, думите, от които може да е
произлязла, ще проверяваме за думи с дължина x-1 получени, като сме премахнали
всяка буква на A поотделно. Тъй като A е със сортирани букви то и думите, който
получаваме чрез премахване на буква от A ще са със сортирани букви, тоест
директно можем да търсим във списъка със думи с дължина x-1.

Последната оптимизация, която ще направим е да сортираме думите с равна дължина
лексикографски и да търсим в тях двоично.
*/



/*
NAME: Ivan Anev
PROG: worch
LANG: C
*/

#include <stdio.h>
#include <string.h>

#define MAXW 250010
#define MAXLEN 32

int wc;
char words[MAXW][MAXLEN], ori[MAXW][MAXLEN];
int ix[MAXW], sl[MAXLEN];
int back[MAXW], len[MAXW];

void readf(void);
void solve(void);
void writef(void);

int main(void) {
    readf();
    solve();
    writef();

    return 0;
}

void readf(void) {
     char word[MAXLEN];
     int l;

     void sortw(char *word);

     while (scanf("%s", word) != -1) {
           l = strlen(word);
           if (l >= 3) {
              strcpy(ori[wc], word);
              sortw(word);
              strcpy(words[wc++], word);
           }
     }
}

void solve(void) {
     int i, j, l, b, k, p;
     char word[MAXLEN], tmp[MAXLEN];

     int searchw(char *w);
     void sortall(void);

     back[0] = -1;
     for (i = 0; i < wc; ++i) {
         back[i] = -1;
         len[i] = 1;
         ix[i] = i;
     }

     sortall();
     p = 3;
     for (i = 0; i < wc; ++i)
         if ((l = strlen(words[ix[i]])) > p) {
            p = l;
            sl[l] = i;
         }
     sl[p+1] = wc;

     for (k = sl[4]; k < wc; ++k) {
         strcpy (word, words[ix[k]]);
         l = strlen(word);
         for (i = 0; i < l; ++i) {
             for (j = 0; j < i; ++j)
                 tmp[j] = word[j];
             while (word[j])
                   tmp[j++] = word[j+1];
             b = searchw(tmp);
             if (b != -1 && len[b] + 1 > len[k]) {
                len[k] = len[b] + 1;
                back[k] = b;
             }
         }
     }
}

void writef(void) {
     int best, i;
     int stack[MAXLEN], sp;

     best = 0;
     for (i = 1; i < wc; ++i)
         if (len[i] > len[best])
            best = i;

     sp = 0;
     while (best != -1) {
           stack[sp++] = best;
           best = back[best];
     }

     if (strlen(ori[ix[stack[sp-1]]]) == 3) {
        while (sp-- > 0)
              printf("%s\n", ori[ix[stack[sp]]]);
     }
}

void sortw(char *word) {
     int i, j, l;
     char t;

     l = strlen(word);
     for (i = 0; i < l; ++i)
         for (j = i+1; j < l; ++j)
             if (word[i] > word[j]) {
                t = word[i];
                word[i] = word[j];
                word[j] = t;
             }
}

int searchw(char *w) {
    int i, l, down, up, mid, r;

    l = strlen(w);
    down = sl[l];
    up = sl[l+1] - 1;
    while (down <= up) {
          mid = (down + up) / 2;
          r = strcmp(words[ix[mid]], w);
          if (r == 0)
             return mid;
          else if (r > 0)
               up = mid - 1;
          else
              down = mid + 1;
    }

    return -1;
}

void sortall(void) {
     int i, j, g, s, l1, l2, t;

     g = wc;
     do {
        s = 0;
        g = (int)(g / 1.3);
        if (g < 1)
           g = 1;
        if (g == 9 || g == 10)
           g = 11;
        for (j = g; j < wc; ++j) {
            i = j - g;
            if ((l1 = strlen(words[ix[i]])) > (l2 = strlen(words[ix[j]]))
                                || l1 == l2 && strcmp(words[ix[i]], words[ix[j]]) > 0) {
               t = ix[i];
               ix[i] = ix[j];
               ix[j] = t;
               s = 1;
            }
        }
     }
     while (g > 1 || s != 0);
}