Online computation of normalized substring complexity

Abstract

The normalized substring complexity $\hat{I}´$ of a string is defined as ${\max }_k\{c[k]/k\}$, where $c[k]$ is the number of \textit{distinct} substrings of length $k$. This simply defined measure has recently attracted attention due to its established relationship to popular string compression algorithms. We consider the problem of computing $\hat{I}´$ online, when the string is provided from a stream. We present two algorithms solving the problem: one working in $O(\log n)$ amortized time per character, and the other in $O({\log }^{3}n)$ worst-case time per character. To our knowledge, this is the first polylog-time online solution to this problem.

16 pages, 1 figure