Algoritmi per la costruzione in tempo lineare di alberi dei suffissi

Un albero dei suffissi è una struttura dati ad albero utilizzata per contenere stringhe in grado di metterne in evidenza la struttura interna, facilitando la soluzione di diversi problemi, o pi ù in generale, permettendo un approccio differente nella loro risoluzione. Gli alberi dei suffissi sono dunque spesso usati per risolvere i problemi che occorrono durante particolari operazioni di ricerca all'interno di testi oppure operazioni di modifica degli stessi. Sono inoltre ampiamente utilizzati in applicazioni inerenti alla bioinformatica, nella ricerca di pattern nel DNA o di sequenze di proteine (che possono essere visualizzate come lunghe stringhe di caratteri). Lo scopo di questa tesi è di approfondire e presentare due algoritmi che permettono di costruire tali alberi in modo efficiente: gli algoritmi di Weiner, presentato nel 1973, e di Ukkonen, del 1995. Sono dunque analizzate tutte le procedure e gli accorgimenti sfruttati da questi algoritmi per raggiungere l'efficienza richiesta