Substring Complexities on Run-length Compressed Strings

Abstract

Let $S_T(k)$ denote the set of distinct substrings of length $k$ in a string $T$, then the $k$-th substring complexity is defined by its cardinality $|S_T(k)|$. Recently, $\delta =\max \{|S_T(k)|/k:k\ge 1\}$ is shown to be a good compressibility measure of highly-repetitive strings. In this paper, given $T$ of length $n$ in the run-length compressed form of size $r$, we show that $\delta$ can be computed in $C_{\mathsf{sort}}(r,n)$ time and $O(r)$ space, where $C_{\mathsf{sort}}(r,n)=O(\min (r\lg \lg r,r{\lg }_{r}n))$ is the time complexity for sorting $r$ $O(\lg n)$-bit integers in $O(r)$ space in the Word-RAM model with word size $\Omega (\lg n)$.