Esta questão já tem uma resposta aqui:

Eu estou fazendo algum trabalho com o algoritmo de Ukkonen para construir árvores de sufixos, mas não estou entendendo algumas partes da explicação do autor por sua complexidade de tempo linear.

Eu aprendi o algoritmo e o codifiquei, mas o papel que eu estou usando como a principal fonte de informação (link abaixo) é meio confuso em algumas partes, então não está muito claro para mim porque o algoritmo é linear.

Qualquer ajuda? Obrigado.

Link para o artigo de Ukkonen:http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf