Cartesian trees and Lyndon trees

12/23/2017
by   Maxime Crochemore, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset