Cartesian and Lyndon trees

Arbres Cartésiens et arbres de Lyndon

Maxime Crochemore (1, 2) , Luís M.S. Russo (3)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 King‘s College London
3 INESC-ID - Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa

The article describes the structural and algorithmic relations between Cartesian trees and Lyndon Trees. This leads to a uniform presentation of the Lyndon table of a word corresponding to the Next Nearest Smaller table of a sequence of numbers. It shows how to efficiently compute runs, that is, maximal periodicities occurring in a word.

Mots clés: Lyndon Tree Cartesian tree runs word; Lyndon Tree; Cartesian tree; runs; word

Domaines: Informatique [cs]

Maxime Crochemore, Luís M.S. Russo. Cartesian and Lyndon trees. Theoretical Computer Science, 2020, 806, pp.1-9. ⟨10.1016/j.tcs.2018.08.011⟩. ⟨hal-04523393⟩