La Cadena de Referencia
Se te proporciona una lista de
n cadenas, cada una compuesta de letras minúsculas del alfabeto latino. Llamaremos a una cadena s, formada por letras minúsculas del alfabeto latino y el carácter #, una cadena de referencia si, para cada cadena en la lista, es posible elegir algún índice i en s tal que ≠ # y, al seleccionar todos los índices desde i hasta la siguiente aparición de # (sin incluirla), se obtenga la cadena correspondiente. La cadena de referencia siempre debe terminar con el carácter #.Escribe un programa que, dada la lista de cadenas, determine la longitud de la cadena de referencia más corta que cumpla con la condición anterior.
Entrada
La primera línea de la entrada contiene un entero
n (1 ≤ n ≤ 100 000), que representa la cantidad de cadenas en la lista.Las siguientes
n líneas contienen dichas cadenas. Cada cadena se compone de letras minúsculas del alfabeto latino y tiene una longitud de, como máximo, 10 caracteres.Salida
El programa debe imprimir un único entero, que representa la longitud de la cadena de referencia más corta que cumpla la condición.
Examples
Entrada | Salida |
6
found
profound
ground
round
wound
und | 22 |
3
ab
bc
cd | 9 |
Explicación
- Ejemplo 1: Una de las cadenas de referencia más cortas es ‘
ground#profound#wound#’
- Ejemplo 2: Una de las cadenas de referencia más cortas es ‘
ab#bc#cd#’
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB