{"ID":2879284,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.16092","arxiv_id":"2508.16092","title":"On the number of MUSs crossing a position","abstract":"A string $w$ is said to be a minimal unique substring (MUS) of a string $T$ if $w$ occurs exactly once in $T$, and any proper substring of $w$ occurs at least twice in $T$. It is known that the number of MUSs in a string $T$ of length $n$ is at most $n$, and that the set $MUS(T)$ of all MUSs in $T$ can be computed in $O(n)$ time [Ilie and Smyth, 2011]. Let $MUS(T,i)$ denote the set of MUSs that contain a position $i$ in a string $T$. In this short paper, we present matching $Θ(\\sqrt{n})$ upper and lower bounds for the number $|MUS(T,i)|$ of MUSs containing a position $i$ in a string $T$ of length $n$.","short_abstract":"A string $w$ is said to be a minimal unique substring (MUS) of a string $T$ if $w$ occurs exactly once in $T$, and any proper substring of $w$ occurs at least twice in $T$. It is known that the number of MUSs in a string $T$ of length $n$ is at most $n$, and that the set $MUS(T)$ of all MUSs in $T$ can be computed in $...","url_abs":"https://arxiv.org/abs/2508.16092","url_pdf":"https://arxiv.org/pdf/2508.16092v1","authors":"[\"Hiroto Fujimaru\",\"Takuya Mieno\",\"Shunsuke Inenaga\"]","published":"2025-08-22T05:14:28Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}