Prefijos P82232


Statement
 

pdf   zip

thehtml

Considera una colección de palabras. A veces, es posible identificar cada palabra de forma unívoca a partir de sus prefijos. Por ejemplo, si la colección es { amor, casa, caso, copa, ya }, una palabra que empiece por a tiene que ser amor. Del mismo modo, si sabemos que una palabra empieza por y, ésta tiene que ser ya. Sin embargo, para identificar la palabra copa necesitamos el prefijo co, y para identificar tanto casa como caso necesitamos escribir las palabras completas.

Tu programa debe escribir las palabras ordenadas crecientemente según la longitud del prefijo más corto que las identifica. En caso de empate, hay que escribir las palabras en orden lexicográfico.

Entrada

La entrada consiste en varios casos. Cada caso comienza con su número de palabras n ≥ 2. Siguen n palabras, cada una con entre 1 y 20 letras minúsculas. Todas las palabras de una colección serán identificables a partir de alguno de sus prefijos (eventualmente, la palabra completa). Es decir, ninguna palabra dada será prefijo de otra del mismo caso.

Salida

Para cada caso, vuestro programa debe escribir los prefijos (junto con las palabras a las que identifican) en orden creciente por longitud y, en caso de empate, en orden lexicográfico. Separar la salida entre casos con una línea con 10 guiones.

Puntuación

  • Test1:  ‍ Pruebas con n ≤ 10.  ‍45 Puntos ‍
  • Test2:  ‍ Pruebas con n ≤ 10000.  ‍55 Puntos ‍
Public test cases
  • Input

    5
    caso
    casa
    copa
    amor
    ya
    
    2
    hola
    adios
    

    Output

    a amor
    y ya
    co copa
    casa casa
    caso caso
    ----------
    a adios
    h hola
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++