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