# A Survey on Shortest Unique Substring Queries
## 3 Position-SUS Queries
### In Place and Compact Data Structures' Approaches  
The suffix tree of a string \(\mathcal{S}\) of length \(n\) occupies space almost 20 times larger than the space needed to store \(\mathcal{S}\), which is \(n\log|\Sigma|\) bits. All aforementioned data structures in Section 3.3 require \(\Theta(n)\) words, where \(n\) is the length of the string \(\mathcal{S}\). When \(n\) is large, the memory usage would be problematic. In order to avoid this issue, [PERSON] et al. [3] proposed a data structure including the input string and two integer arrays for storing the starting positions and ending positions of \(\mathsf{SUS}\)s. The preprocessing time for their algorithm is linear and takes \(\mathcal{O}(\log n)\) bits of additional working space. If we want to consider the space needed to store all \(\mathsf{SUS}\)s for all positions, their algorithm takes the least amount of space to do that, which is \(2n\) words to maintain the starting and ending positions of \(\mathsf{SUS}\)s and another \(n\) bytes to store the input string. Previous works need \(\mathcal{O}(n)\) space while the hidden constant is large; however, that overhead does not exist in [PERSON] et al. 's work. They use suffix arrays instead of suffix trees in their construction. Moreover, they handle all computations in the place of two integer arrays. As a result, their algorithm can find the position-\(\mathsf{SUS}\) for every string position in \(\mathcal{O}(n)\) time. There was still a question of whether we can solve \(\mathsf{SUS}\) problem in sub-linear space. To answer this question, [PERSON] et al. [18] presented the first time-space trade off algorithm which uses \(\mathcal{O}(n/\tau)\) words of additional space. Given a position \(p\in\{1\cdots n\}\), their algorithm answers Problem 1 in \(\mathcal{O}(n\tau^{2}\log\frac{n}{\tau})\) time, where parameter \(\tau\geq 1\). Another query is reporting \(\mathsf{SUS}\)s for all positions of \(\mathcal{S}\). For this type of query, they present an \(\mathcal{O}(n\tau^{2}\log n)\) algorithm using \(\mathcal{O}(n/\tau)\) words and \(4n+o(n)\) bits of additional working space. In addition to these deterministic algorithms, they present a randomized algorithm in which the time complexity is \(\mathcal{O}(n\tau\log^{c+1}n)\) by using additional \(n/\log^{c}n\) words, where \(c\geq 0\) is an arbitrary constant. There is a chance of at most \(n^{-\mathcal{O}(1)}\) that the reported substring is unique and covers the query position but not the shortest one. In their deterministic algorithms, their intuition is that each \(\mathsf{SUS}\) for a position \(k\) is definitely the shortest unique prefix of \(\mathcal{S}[i,n]\) for some \(i\leq k\), or the smallest right extension till position \(k\) of such prefix. For each suffix \(\mathcal{S}[i,n]\), they define \(\mathsf{LS}_{i}\) as the shortest unique prefix of \(\mathcal{S}[i,n]\). In order to reduce the space complexity, instead of storing \(\mathsf{LS}_{i}\)s for all \(\mathcal{S}[i,n]\), \(i\in\{1\cdots n\}\), they choose a set of \(\mathcal{O}(n/\tau)\) suffixes and compute the corresponding \(\mathsf{LS}\)s. After computing all the \(\mathsf{LS}\)s of the suffixes in the chosen set, using a brute force approach, for any suffix \(\mathcal{S}[j,n]\), they can compute \(\mathsf{LS}_{j}\). Their results are summarized in Theorem 5. Theorem 5 ([18]): _For any given string position \(p\in\{1\cdots n\}\), an \(\mathsf{SUS}\) covering \(p\) can be computed in \(\mathcal{O}(n\tau^{2}\log\frac{n}{\tau})\) time and additional \(\mathcal{O}(n/\tau)\) working space. In addition, computing any \(\mathsf{SUS}\) for every position in the string can be reported in \(\mathcal{O}(n\tau^{2}\log n)\) time and additional \(\mathcal{O}(n/\tau)\) words and \(4n+o(n)\) bits of additional working space._  
[PERSON] et al. 's algorithm reports only one \(\mathsf{SUS}\) for each given query. In 2019, [PERSON] et al.