2020/11/25 by Badkobeh, Golnaz, Crochemore, Maxime
#68W27 #68W32 #Data Structures and Algorithms (cs.DS) #E.1 #F.2.2 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2011.12742
We extend the left-to-right Lyndon factorisation of a word to the left Lyndon tree construction of a Lyndon word. It yields an algorithm to sort the prefixes of a Lyndon word according to the infinite ordering defined by Dolce et al. (2019). A straightforward variant computes the left Lyndon forest of a word. All algorithms run in linear time on a general alphabet, that is, in the letter-comparison model.