Cartesian and Lyndon trees
From MaRDI portal
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.
Recommendations
- Lyndon trees
- A new characterization of maximal repetitions by Lyndon trees
- Linear construction of a left Lyndon tree
- Lyndon words, permutations and trees.
- Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée. (Generation of a section of conjugation classes and trees of Lyndon words of bounded length)
Cites work
- scientific article; zbMATH DE number 3811868 (Why is no real title available?)
- scientific article; zbMATH DE number 140492 (Why is no real title available?)
- A unifying look at data structures
- Algorithms on Strings
- Faster longest common extension queries in strings over general alphabets
- Lyndon words, permutations and trees.
- Near-optimal computation of runs over general alphabet via non-crossing LCE queries
- Suffix array and Lyndon factorization of a text
- The maximal number of cubic runs in a word
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
Cited in
(9)- Lyndon partial words and arrays with applications
- String rearrangement inequalities and a total order between primitive words
- Historical lattice trees
- scientific article; zbMATH DE number 7559170 (Why is no real title available?)
- On generalized Lyndon words
- Range minimum queries in minimal space
- Linear construction of a left Lyndon tree
- Inducing the Lyndon array
- Approximate Cartesian tree matching: an approach using swaps
This page was built for publication: Cartesian and Lyndon trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2285120)
