Konstruksi pohon sufiks linear-waktu yang sederhana secara konseptual

Pada tahun 1973 Weiner memberikan pembangunan pohon akhiran linear pertama kali. Algoritma disederhanakan pada tahun 1976 oleh McCreight, dan pada tahun 1995 oleh Ukkonen. Namun demikian, saya menemukan algoritma Ukkonen relatif terlibat secara konseptual.

Apakah ada penyederhanaan pada algoritma Ukkonen sejak 1995?

Saya tidak yakin apakah ada hasil baru yang secara langsung menyederhanakan pembangunan pohon sufiks. Namun, setidaknya ada satu hasil yang memberikan algoritma yang sangat sederhana untuk membangun susunan sufiks dalam waktu linier.

$\cal{O}(1)$

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

Selain apa yang disebutkan ( Kärkkäinen & Sanders, 2003 ), saya pikir Anda akan menghargai versi "yang lebih baru" oleh Kärkkäinen, Sanders dan Burkhard, 2006 . Algoritma pada dasarnya mengikuti struktur algoritma Farach. Ini bisa dibilang lebih sederhana secara konseptual, tetapi bonus sebenarnya adalah mereka memberikan pembaca dengan implementasi algoritma. Hanya sekitar 50 baris C ++, jadi memang tidak ada detail tersembunyi.