Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Reconstructing a suffix array

Franěk, F. and Smyth, W.F. (2005) Reconstructing a suffix array. In: The Prague Stringology Conference 2005, 29 - 31 August 2005, Czech Technical University, Prague



For certain problems (for example, computing repetitions and repeats, data compression applications) it is not necessary that the suffixes of a string represented in a suffix tree or suffix array should occur in lexicographical order (lexorder). It thus becomes of interest to study possible alternate orderings of the suffixes in these data structures, that may be easier to construct or more efficient to use. In this paper we consider the "reconstruction" of a suffix array based on a given reordering of the alphabet, and we describe simple time- and space-efficient algorithms that accomplish it.

Item Type: Conference Paper
Conference Website:
Item Control Page Item Control Page


Downloads per month over past year