On the number of MUSs crossing a position

August 22, 2025 Β· Declared Dead Β· πŸ› SPIRE

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Hiroto Fujimaru, Takuya Mieno, Shunsuke Inenaga arXiv ID 2508.16092 Category cs.DS: Data Structures & Algorithms Citations 0 Venue SPIRE Last Checked 4 months ago
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$.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted