On the number of MUSs crossing a position
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909748738129920 |
|---|---|
| author | Fujimaru, Hiroto Mieno, Takuya Inenaga, Shunsuke |
| author_facet | Fujimaru, Hiroto Mieno, Takuya Inenaga, Shunsuke |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_16092 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the number of MUSs crossing a position Fujimaru, Hiroto Mieno, Takuya Inenaga, Shunsuke Data Structures and Algorithms 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$. |
| title | On the number of MUSs crossing a position |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.16092 |