Catena di parole

Correttore online – Intermedi

Una catena di parole di lunghezza n è una sequenza w1, w2, … , wn di parole in cui per ogni i (0 < i < n) la parola wi è un prefisso proprio della parola wi+1.
Si ricorda che una parola u di lunghezza k è un prefisso proprio della parola v di lunghezza h se h > k e le prime k lettere di v sono esattamente le stesse della parola u.
E’ dato un insieme di parole S = {s1, s2, …, sm}.
Trovare la catena di parole di lunghezza massima che può essere costruita usando le parole di questo insieme.

Dati di input

La prima linea contiene un numero intero m (0 < m < 256).
Ciascuna delle successive m linee contiene una parola dell’insieme S.
Ogni parola consiste di una sequenza di n lettere minuscole dell’alfabeto latino, con 0 < n < 256.

Dati di output

Produrre la lunghezza massima della catena di parole che può essere costruita con le parole di S.

Esempi di input/output

input.txt output.txt
3
a
ab
abc
3
5
a
ab
bc
bcd
add
2

Autore/i: A.S. Stankevich, ACM ICPC Team St. Petersburg State University of Information technology, Mechanics and Optics.


Utilizza le funzioni di string

Notice: This work is licensed under a BY-NC-SA. Permalink: Catena di parole

Lascia un commento