# A Survey on Shortest Unique Substring Queries
## 1 Introduction  
Let \(\mathcal{S}\) be a string of length \(n\) and \(\mathcal{S}[i,j]\) be the substring which starts at position \(i\) and ends at position \(j\) of \(\mathcal{S}\). The substring \(\mathcal{S}[i,j]\) is a repeat if it occurs more than once in \(\mathcal{S}\); otherwise, it is a unique substring of \(\mathcal{S}\). Since finding the shortest unique substrings is a non-trivial problem that has several applications for different purposes, variants of this problem have been studied. Table 1 shows the variants of the Shortest Unique Substring (SUS) problem that we focused on in this survey. In 2005, [PERSON] et al. [19] explained how the shortest unique substring is a useful construct for alignment-free genome comparison. Unique substrings can help to determine the distinctness and difference between a group of closely related organisms [1, 19]. In addition, an algorithm for finding a unique substring can be helpful to build a unique genetic fingerprint from a DNA sample or can help designing polymerase chain reaction (PCR) primer technique in molecule biology [1, 20]. In 2015, [PERSON] et al. [21] investigated the usage of shortest unique substrings for alignment and compression of DNA sequences. In addition to the applications in bioinformatics, the shortest unique substrings can be used in information retrieval for document search. The _position based shortest unique substring (position-SUS) queries_ was first proposed by [PERSON] et al. [1]. Given a string \(\mathcal{S}\) of length \(n\) and a query point \(p\) in the string, the problem is to find a shortest unique substring covering \(p\). They presented an algorithm which costs \(\mathcal{O}(n^{2})\) time and \(\mathcal{O}(n)\) space. In 2014, several publications have revisited this problem. [PERSON] et al. [6] and [PERSON] et al. [13] proposed an optimal \(\mathcal{O}(n)\) time and space algorithm for solving this problem. In addition, [PERSON] et al. [3] and [PERSON] et al. [18] presented compact data \begin{table}
\begin{tabular}{l l l l} \hline \hline  & \multicolumn{3}{c}{**Variant SUS Queries**} \\ \hline
**Position-SUS** & **Interval-SUS** & **Approximate-SUS** & **Palindromic-SUS** & **Range-SUS** \\ \hline [PERSON] et al. 2013 [1] & [PERSON] et al. [2] & [PERSON] et al. 2017 [3] & [PERSON] et al. 2018 [4] & [PERSON] et al. 2019 [5] \\ [PERSON] et al. 2014, 2015 [6,7] & [PERSON] et al. 2016 [8] & [PERSON] et al. 2018, 2020 [9,10] & [PERSON] et al. 2019, 2020 [11, 12] \\ [PERSON] et al. 2014 [13] & [PERSON] et al. 2019 [14] & [PERSON] et al. 2018, 2020 [15,16] & \\ [PERSON] et al. 2015, 2020 [17,37] & 2017 & 2018 & \\ [PERSON] et al. 2016 [18] & & & \\ [PERSON] et al. 2019 [14] & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: This table categorizes the main papers which are reviewed and discussed in this survey. structures that can answer a position-\(\mathsf{SUS}\) query using less than \(2n\) words of space, where a word size is \(\Omega(\log n)\). Several variations of the original problem have been proposed in the following years. In 2014, [PERSON] et al. [2] generalized the position-\(\mathsf{SUS}\) problem by considering the positions in an interval rather than a single position in the string. For the _interval-\(\mathsf{SUS}\)_ problem, they preprocess the input string in \(\mathcal{O}(n)\) time and space to answer any interval \(\mathsf{SUS}\) query in constant time and return all \(\mathsf{SUS}\)s in \(\mathcal{O}(occ)\) time, where \(occ\) is the number of outputs. In 2019, [PERSON] et al. [14] improved the space complexity of this problem by providing a compact data structure. In 2016, [PERSON] et al. [8] considered \(\mathsf{SUS}\) queries on _run-length encoded(RLE)_ strings. Their motivation was to reduce space and time complexity of processing the input string.