Fully-functional bidirectional Burrows-Wheeler indexes

Fabio Cunial, Djamal Belazzougui

Given a string $T$ on an alphabet of size $\sigma$, we describe a bidirectional Burrows-Wheeler index that takes $O(|T|\log \sigma )$ bits of space, and that supports the addition \emph{and re…