Computing the longest common prefix array based on the Burrows–Wheeler transform

AbstractMany 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