La Stringa di Riferimento
Hai a disposizione un elenco di
n stringhe, ognuna composta da lettere minuscole dell’alfabeto latino. Definiamo una stringa s, formata da lettere minuscole dell’alfabeto latino e dal carattere #, una stringa di riferimento se, per ogni stringa nell’elenco, è possibile scegliere un indice i in s tale che ≠ # e, selezionando tutti gli indici da i fino alla successiva occorrenza di # (esclusa), si ottenga la stringa corrispondente. La stringa di riferimento deve sempre terminare con il carattere #.Scrivi un programma che stabilisca la lunghezza della stringa di riferimento più breve che soddisfa questa condizione, data la lista di stringhe.
Ingresso
La prima riga dell’ingresso contiene un intero
n (1 ≤ n ≤ 100 000), che rappresenta il numero di stringhe nell’elenco.Le successive
n righe contengono le stringhe. Ogni stringa è composta da lettere minuscole dell’alfabeto latino e ha una lunghezza di al massimo 10.Uscita
Il programma deve stampare un singolo intero, che è la lunghezza della stringa di riferimento più breve che soddisfa la condizione.
Esempi
Ingresso | Uscita |
6
found
profound
ground
round
wound
und | 22 |
3
ab
bc
cd | 9 |
Spiegazione
- Esempio 1: una delle stringhe di riferimento più brevi è “ground#profound#wound#”.
- Esempio 2: una delle stringhe di riferimento più brevi è “ab#bc#cd#”.
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB