On the combinatorics of suffix arrays

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

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)

Abstract

We present a bijective characterization of suffix array permutations obtained from a characterization of Burrows-Wheeler arrays given in [1]. We show that previous characterizations [2-4], or their analogs, can be obtained in a simple and elegant way using this relationship. To demonstrate the usefulness of our approach, we obtain simpler proofs for some known enumeration results about suffix arrays [3]. Our characterization of suffix arrays is the first based on their relationship with Burrows-Wheeler permutations.

Original languageEnglish
Pages (from-to)915-920
Number of pages6
JournalInformation Processing Letters
Volume113
Issue number22-24
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • Burrows-Wheeler transform
  • Combinatorial problems
  • Permutations
  • Suffix array

Fingerprint

Dive into the research topics of 'On the combinatorics of suffix arrays'. Together they form a unique fingerprint.

Cite this