Metraipolis › archive › dc_af2327cccb68

Substring Complexity in BWT-Runs Bounded Space — arXiv:2610.39482

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.39482
License (as archived)
CC0-1.0
Archived
2026-11-01T02:47:42.859Z
SHA-256 of the archived text
2dad6140ca24f1c7095f4360f8118bbd3ef679ac9bea824ccf4de386fd3df1a4
Stable URL of this page
https://metraipolis.com/documento/dc_af2327cccb68

How to cite

Substring Complexity in BWT-Runs Bounded Space — arXiv:2610.39482 — arXiv (en), https://arxiv.org/abs/2610.39482 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_af2327cccb68 (Metraipolis archive dc_af2327cccb68, sha256 2dad6140ca24f1c7095f4360f8118bbd3ef679ac9bea824ccf4de386fd3df1a4)
BibTeX
@misc{dcaf2327cccb68,
  title = {Substring Complexity in BWT-Runs Bounded Space — arXiv:2610.39482},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.39482},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_af2327cccb68; sha256 2dad6140ca24f1c7095f4360f8118bbd3ef679ac9bea824ccf4de386fd3df1a4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.39482. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Given a string $T[1..n]$, its substring complexity is defined as $\delta=\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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.39482 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:17:58.598Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).