Construções de árvore de sufixo em tempo linear conceitualmente simples

Em 1973, Weiner deu a primeira construção em tempo linear de árvores com sufixo. O algoritmo foi simplificado em 1976 por McCreight e em 1995 por Ukkonen. No entanto, acho o algoritmo de Ukkonen relativamente envolvido conceitualmente.

Houve simplificações no algoritmo de Ukkonen desde 1995?

Não tenho certeza se houve novos resultados simplificando diretamente a construção de árvores com sufixo. No entanto, houve pelo menos um resultado fornecendo um algoritmo muito simples para a construção de matrizes de sufixos em tempo linear.

$\cal{O}(1)$

$\cal{O}(n \lg n)$

Além do que foi mencionado ( Kärkkäinen & Sanders, 2003 ), acho que você apreciaria a versão "mais recente" de Kärkkäinen, Sanders e Burkhard, 2006 . O algoritmo basicamente segue a estrutura do algoritmo de Farach. É sem dúvida conceitualmente mais simples, mas o verdadeiro bônus é que eles fornecem ao leitor uma implementação do algoritmo. São apenas cerca de 50 linhas de C ++, portanto não há detalhes ocultos.