Prague Stringology Conference 2020
Golnaz Badkobeh and Maxime Crochemore
Left Lyndon Tree Construction
| Abstract: |
| 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 (letter-comparison model). |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |