{"ID":2853398,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.16454","arxiv_id":"2510.16454","title":"Online computation of normalized substring complexity","abstract":"The normalized substring complexity $δ$ 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 $δ$ 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.","short_abstract":"The normalized substring complexity $δ$ 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 prob...","url_abs":"https://arxiv.org/abs/2510.16454","url_pdf":"https://arxiv.org/pdf/2510.16454v2","authors":"[\"Gregory Kucherov\",\"Yakov Nekrich\"]","published":"2025-10-18T11:23:17Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}