Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing

Philip Bille, Mikko Berggren Ettienne, Inge Li Gørtz +1

Given a string $S$, the \emph{compressed indexing problem} is to preprocess $S$ into a compressed representation that supports fast \emph{substring queries}. The goal is to use lit…