Cartesian and Lyndon trees
Arbres Cartésiens et arbres de Lyndon
Abstract
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.
Origin | Files produced by the author(s) |
---|