Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430892 | Journal of Discrete Algorithms | 2013 | 10 Pages |
Abstract
Many sequence analysis tasks can be accomplished with a suffix array, and several of them additionally need the longest common prefix array. In large scale applications, suffix arrays are being replaced with full-text indexes that are based on the Burrows–Wheeler transform. In this paper, we present the first algorithm that computes the longest common prefix array directly on the wavelet tree of the Burrows–Wheeler transformed string. It runs in linear time and a practical implementation requires approximately 2.2 bytes per character.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Timo Beller, Simon Gog, Enno Ohlebusch, Thomas Schnattinger,