Journal article
Reconstructing a suffix array
International Journal of Foundations of Computer Science, Vol.17(06), pp.1281-1295
2006
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.
Details
- Title
- Reconstructing a suffix array
- Authors/Creators
- F. Franěk (Author/Creator) - McMaster UniversityW.F. Smyth (Author/Creator) - McMaster University
- Publication Details
- International Journal of Foundations of Computer Science, Vol.17(06), pp.1281-1295
- Publisher
- World Scientific Publishing Co.
- Identifiers
- 991005540673107891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
50 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science