Catena di parole

Correttore online – Intermedi

Una catena di parole di lunghezza n è una sequenza w₁, w_{2, … ,} w_n di parole in cui per ogni i (0 < i < n) la parola w_i è un prefisso proprio della parola w_i+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 = {s₁, s₂, …, s_m}.
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

/*
   www.valcon.it
   Correttore online - Intermedi - Catena di parole
*/

#include
#include
#include
#include
#define NMAX 256

using namespace std;

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
	int 	 N;
	string   parole[NMAX];
	int		 conta,
	   		 MAX=0;
		
	fin >> N;	
	for(int i=0; i < N; i++)
		fin >> parole[i];					
	sort(parole, parole+N);		// in ordine lessicografico	
			
	conta=1;					// trova la catena più lunga
	for(int i=0; i < N-1; i++)
	{		
	    // confronta la parola i-esima con la successiva, solo i caratteri effettivi
		int c=parole[i].compare(0, parole[i].length(), parole[i+1], 0, parole[i].length());
	    
		if(c == 0)   
			conta++;
		else
		{
 			if(conta > MAX)
				MAX=conta;
			conta=1; 
		}
	}
	if(conta > MAX)				// se anche l'ultimo confronto ha successo
		MAX=conta;

	fout << MAX;
}