RECONSTRUCTING A SUFFIX ARRAY Conferences

abstract

• 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.

authors

• Franek, Frantisek
• Smyth, William

status

• published 

publication date

• December 2006

has subject area

• 08 Information and Computing Sciences (FoR)
• Computation Theory & Mathematics (Science Metrix)

published in

• International Journal of Foundations of Computer Science  Journal

presented at event

• Prague Stringology Conference 2005  Conference

keywords

• Computer Science
• Computer Science, Theory & Methods
• LINEAR-TIME CONSTRUCTION
• Science & Technology
• Technology
• alphabet
• lexicographic order
• string
• suffix array
• suffix tree

Digital Object Identifier (DOI)

• 10.1142/s0129054106004418

start page

• 1281

end page

• 1295

volume

• 17

issue

• 06