algorithm - array - Entendiendo el algoritmo de Ukkonen para árboles de sufijos
suffix tree c++ (1)
Encuentra una copia del libro de texto de algoritmos de cuerdas de Gusfield. Tiene la mejor exposición de la construcción del árbol de sufijos que he visto. La linealidad es una consecuencia sorprendente de una serie de optimizaciones del algoritmo de alto nivel.
Esta pregunta ya tiene una respuesta aquí:
Estoy trabajando con el algoritmo de Ukkonen para construir árboles de sufijos, pero no entiendo algunas partes de la explicación del autor por su complejidad de tiempo lineal.
Aprendí el algoritmo y lo codifiqué, pero el documento que utilizo como la principal fuente de información (enlace a continuación) es algo confuso en algunas partes, por lo que no me queda claro por qué el algoritmo es lineal.
¿Alguna ayuda? Gracias.
Enlace al artículo de Ukkonen: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf