Fast Compressed Self-Indexes with Deterministic Linear-Time Construction

J. Ian Munro, Gonzalo Navarro, Yakov Nekrich

We introduce a compressed suffix array representation that, on a text $T$ of length $n$ over an alphabet of size $\sigma$, can be built in $O(n)$ deterministic time, within $O(n\log \sigma )$…