Substring Complexity in BWT-Runs Bounded Space

Abstract

Given a string $T[1..n]$, its substring complexity is defined as $δ=\max_k d_k/k$, where $d_k$ is the number of its distinct substrings of length $k$ in $T$. We show how to compute it in $O(n+r\log r)$ time, using only $O(r)$ words of space, where $r$ denotes the number of runs in the Burrows-Wheeler transform.