Construcciones de árbol de sufijos de tiempo lineal conceptualmente simples

En 1973 Weiner dio la primera construcción en tiempo lineal de árboles sufijos. El algoritmo fue simplificado en 1976 por McCreight, y en 1995 por Ukkonen. Sin embargo, encuentro el algoritmo de Ukkonen relativamente involucrado conceptualmente.

¿Ha habido simplificaciones en el algoritmo de Ukkonen desde 1995?

No estoy seguro de si hubo nuevos resultados que simplifiquen directamente la construcción de árboles de sufijos. Sin embargo, ha habido al menos un resultado que proporciona un algoritmo muy simple para construir matrices de sufijos en tiempo lineal.

Tenga en cuenta que hay más de una equivalencia conceptual entre estas dos estructuras de datos, ya que puede usar una matriz de sufijos (con tiempo para consultar el prefijo común más largo) para construir un árbol de sufijos equivalente. Este debería ser un ejercicio relativamente simple, pero puedo dar más detalles si es necesario.$\cal{O}(1)$

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

Además de lo mencionado ( Kärkkäinen & Sanders, 2003 ), creo que agradecería la versión "más nueva" de Kärkkäinen, Sanders y Burkhard, 2006 . El algoritmo básicamente sigue la estructura del algoritmo de Farach. Podría decirse que es conceptualmente más simple, pero la verdadera ventaja es que proporcionan al lector una implementación del algoritmo. Son solo unas 50 líneas de C ++, por lo que no hay detalles ocultos.