On the combinatorics of suffix arrays

Gregory Kucherov, Lilla Tóthmérész, Stéphane Vialette

We prove several combinatorial properties of suffix arrays, including a characterization of suffix arrays through a bijection with a certain well-defined class of permutations. Our…