Online computation of normalized substring complexity

Gregory Kucherov, Yakov Nekrich

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 define…