algorithm - array - suffix tree



Comprensione dell'algoritmo di Ukkonen per gli alberi di suffisso (1)

Questa domanda ha già una risposta qui:

Sto facendo un po 'di lavoro con l'algoritmo di Ukkonen per costruire alberi di suffisso, ma non sto capendo alcune parti della spiegazione dell'autore per la sua complessità lineare-temporale.

Ho imparato l'algoritmo e l'ho codificato, ma la carta che sto usando come fonte principale di informazioni (link qui sotto) è un po 'confusa in alcune parti quindi non è chiaro per me perché l'algoritmo sia lineare.

Qualsiasi aiuto? Grazie.

Link al documento di Ukkonen: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf


Trova una copia del manuale di Algoritmi a stringa di Gusfield. Ha la migliore esposizione della costruzione dell'albero dei suffissi che ho visto. La linearità è una conseguenza sorprendente di una serie di ottimizzazioni dell'algoritmo di alto livello.





suffix-tree