Space-efficient Algorithms For Computing Minimal/shortest Unique Substrings

Mieno Takuya, Köppl Dominik, Nakashima Yuto, Inenaga Shunsuke, Bannai Hideo, Takeda Masayuki. Arxiv 2019

[Paper]    
ARXIV

Given a string $T$ of length $n$, a substring $u=T[i..j]$ of $T$ is called a shortest unique substring (SUS) for an interval $[s,t]$ if (a) $u$ occurs exactly once in $T$, (b) $u$ contains the interval $[s,t]$ (i.e. $i\le s\le t\le j$), and (c) every substring $v$ of $T$ with $|v|<|u|$ containing $[s,t]$ occurs at least twice in $T$. Given a query interval $[s,t]\subset [1,n]$, the interval SUS problem is to output all the SUSs for the interval $[s,t]$. In this article, we propose a $4n+o(n)$ bits data structure answering an interval SUS query in output-sensitive $O(\mathit{occ})$ time, where $\mathit{occ}$ is the number of returned SUSs. Additionally, we focus on the point SUS problem, which is the interval SUS problem for $s=t$. Here, we propose a $\lceil (lo{g}_{2}3+1)n\rceil +o(n)$ bits data structure answering a point SUS query in the same output-sensitive time. We also propose space-efficient algorithms for computing the minimal unique substrings of $T$.

Similar Work

• Approximate Nearest Neighbors In Limited Space
• Asymptotic Improvement Of The Gilbert-varshamov Bound On The Size Of Binary Codes
• Near Neighbor Who Is The Fairest Of Them All
• Pattern Matching In Lempel-ziv Compressed Strings Fast Simple And Deterministic