Journal
THEORETICAL COMPUTER SCIENCE
Volume 387, Issue 3, Pages 258-272Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2007.07.017
Keywords
suffix arrays; Burrows-Wheeler transform
Categories
Ask authors/readers for more resources
We propose a fast and memory-efficient algorithm for lexicographically sorting the suffixes of a string, a problem that has important applications in data compression as well as string matching. Our algorithm eliminates much of the overhead of previous specialized approaches while maintaining their robustness for degenerate inputs. For input size n, our algorithm operates in only two integer arrays of size n, and has worst-case time complexity O(n log n). We demonstrate experimentally that our algorithm has stable performance compared with other approaches. (c) 2007 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available