← 研踪 PaperTrailarXiv:2610.39482 · v1
Substring Complexity in BWT-Runs Bounded Space
首次提交 2026-10-29 14:48
版本更新 2026-10-29 14:48
雷达观测 2026-10-30 11:25
摘要
Given a string $T[1..n]$, its substring complexity is defined as $δ=\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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-29 14:48 · 最新观测版本
Substring Complexity in BWT-Runs Bounded Space
Given a string $T[1..n]$, its substring complexity is defined as $δ=\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.
查看此版本解读 →查看此版本原文 ↗