期刊
THEORETICAL COMPUTER SCIENCE
卷 387, 期 3, 页码 258-272出版社
ELSEVIER
DOI: 10.1016/j.tcs.2007.07.017
关键词
suffix arrays; Burrows-Wheeler transform
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据