Left Lyndon tree construction

Badkobeh, Golnaz and Crochemore, Maxime. 2020. Left Lyndon tree construction. Prague Stringology, pp. 84-95. [Article]

[img]
Preview
Text
LeftLyndonTree_PSC20.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial.

Download (232kB) | Preview

Abstract or Description

We extend the left-to-right Lyndon factorisation of a word to the left Lyn-don 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).

Item Type:

Article

Departments, Centres and Research Units:

Computing

Dates:

DateEvent
June 2020Accepted

Item ID:

29992

Date Deposited:

27 Apr 2021 10:45

Last Modified:

10 Jun 2021 15:09

Peer Reviewed:

Yes, this version has been peer-reviewed.

URI:

https://research.gold.ac.uk/id/eprint/29992

View statistics for this item...

Edit Record Edit Record (login required)