Cartesian and Lyndon trees

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.

Authors

• Maxime Crochemore
• Luís M.S. Russo

Keywords

• Lyndon tree
• Cartesian tree
• Runs
• Word