A note on Sturmian words

Dominique Perrin (1) , Antonio Restivo (2)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Dipartimento di Matematica e Informatica [Palermo]

We describe an algorithm which, given a factor of a Sturmian word, computes the next factor of the same length in the lexicographic order in linear time. It is based on a combinatorial property of Sturmian words which is related with the Burrows-Wheeler transformation.

Mots clés: combinatorics

Domaines: Algorithme et structure de données [cs.DS]

Dominique Perrin, Antonio Restivo. A note on Sturmian words. Theoretical Computer Science, 2012, 429 (1), pp.265-272. ⟨10.1016/j.tcs.2011.12.047⟩. ⟨hal-00828351⟩