Let A be an array of n elements taken from a totally ordered set. We present a data structure
of size 3 n+ o (n) bits that allows us to answer the following queries on A in constant time …

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 …

Parallelism is the key to achieving high performance in computing. However, writing efficient
and scalable parallel programs is notoriously difficult, and often requires significant …

We present parallel algorithms for wavelet tree construction with polylogarithmic depth,
improving upon the linear depth of the recent parallel algorithms by Fuentes-Sepulveda et …

Suffix arrays and the corresponding longest common prefix (LCP) array have wide
applications in bioinformatics, information retrieval and data compression. In this work, we …

The suffix array is frequently augmented with the longest-common-prefix (LCP) array that
stores the lengths of the longest common prefixes between lexicographically adjacent …

Finding repetitive structures in genomes and proteins is important to understand their
biological functions. Many data compressors for modern genomic sequences rely heavily on …

One of the most important data structures for string processing—the suffix array—needs to
be augmented with the longest-common-prefix (LCP) array in numerous applications. We …

Motivation: Maximal exact matches, or just MEMs, are a powerful tool in the context of
multiple sequence alignment and approximate string matching. The most efficient algorithms …

The suffix tree is a very important data structure in string processing, but typical
implementations suffer from huge space consumption. In large-scale applications …