Online computation of normalized substring complexity
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908836562993152 |
|---|---|
| author | Kucherov, Gregory Nekrich, Yakov |
| author_facet | Kucherov, Gregory Nekrich, Yakov |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_16454 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online computation of normalized substring complexity Kucherov, Gregory Nekrich, Yakov Data Structures and Algorithms F.2.2 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. |
| title | Online computation of normalized substring complexity |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2510.16454 |