Compressed Index with Construction in Compressed Space

Dmitry Kosolobov

Suppose that we are given a string $s$ of length $n$ over an alphabet $\{0,1,\dots ,n^{O(1)}\}$ and $\delta$ is the string complexity of $s$, a known compression measure. We describe an…