Entendendo o algoritmo do Ukkonen para árvores de sufixo [duplicado]
Esta questão já tem uma resposta aqui:
Algoritmo de árvore de sufixo de Ukkonen em inglês claro 6 respostasEu 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