Compressed suffix array

In computer science, a compressed suffix array is a compressed data structure for pattern matching. Compressed suffix arrays are a general class of data structure that improve on the suffix array. These data structures enable quick search for an arbitrary string with a comparatively small index.

Given a text T of n characters from an alphabet Σ, a compressed suffix array supports searching for arbitrary patterns in T. For an input pattern P of m characters, the search time is typically O(m) or O(m + log(n)). The space used is typically ${\displaystyle O(nH_{k}(T))+o(n)}$, where ${\displaystyle H_{k}(T)}$ is the k-th order empirical entropy of the text T. The time and space to construct a compressed suffix array are normally ${\displaystyle O(n)}$.

...
Wikipedia