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 $\Theta (\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$.

Accepted for SPIRE 2025 (short paper)