# A Survey on Shortest Unique Substring Queries
## 3 Position-SUS Queries
### Linear Time Approaches
#### 3.3.1 [PERSON] et al.'s Framework  
Their framework includes two cases; \(\mathsf{SUS}\) finding for one position, and \(\mathsf{SUS}\) finding for every position. In the first case, they present an algorithm for finding all the \(\mathsf{SUS}\)s covering a specific location \(p\) in \(\mathcal{O}(n)\) time. Similar to the approach explained in Section 3.2, they make this observation that each \(\mathsf{SUS}\) is an extension of an \(\mathsf{LSUS}\). Instead of using suffix tree structure to find \(\mathsf{LSUS}\)s, they use inverse suffix array and \(\mathsf{lcp}\) array to compute \(\mathsf{LSUS}(i)\) for \(i=1,2,\cdots n\) as follows:  
\[\mathsf{LSUS}(i)=\begin{cases}\mathcal{S}[i,i+l_{i}]&if\ i+l_{i}\leq n\\ null&otherwise\end{cases},\]  
where \(l_{i}=\max\{\mathsf{lcp}[\mathsf{SA}^{-1}[i]],\mathsf{lcp}[\mathsf{SA}^{-1}[i ]+1]\}\) and \(null\) means \(\mathsf{LSUS}\) does not exist. Using the above equation, for each string position \(p\), they simply compute \(\mathsf{LSUS}(1)\cdots,\mathsf{LSUS}(p)\) in \(\mathcal{O}(p)\) time and maintain the shortest one for position \(p\). Note that, if for some \(k<p\), \(\mathsf{LSUS}(k)\) does not cover \(p\), we can extend it up to position \(p\). In case of multiple shortest answers, they keep the leftmost candidate. Then, by Lemma 1, they prove their first theorem as follows:  
**Theorem 2** ([6]).: _For any location \(p\) in the string \(\mathcal{S}\), they can find \(\mathsf{SUS}\) covering \(p\) using \(\mathcal{O}(n)\) time and space. If multiple answers exist, the leftmost one is returned._  
In the second case, they extend their algorithm to find all the \(\mathsf{SUS}\)s for every location \(p\in\{1,2\cdots n\}\). Instead of iteratively running the algorithm for finding a \(\mathsf{SUS}\) of a specific position \(n\) times, they use the following lemma to reduce the time complexity to the amortized cost for finding each \(\mathsf{SUS}\) in \(\mathcal{O}(1)\) time.  
**Lemma 2** ([6]).: _For any \(k\in\{2,3,\cdots,n\}\), if \(\mathsf{SUS}\) for position \(k\) is an extension of an \(\mathsf{LSUS}\), then (1) \(\mathsf{SUS}\) for position \(k-1\) must be a substring whose right boundary is the character \(\mathcal{S}[k-1]\), and (2) \(\mathsf{SUS}\) for position \(k\) is the substring \(\mathsf{SUS}\) for position \(k-1\) appended by the character \(\mathcal{S}[k]\)._  
For finding \(\mathsf{SUS}\) of every position, they begin with \(\mathsf{SUS}\) of the first position which is \(\mathsf{LSUS}\) of that position; then, by Lemma 2, they compute \(\mathsf{SUS}\) of position \(k\) using the already calculated \(\mathsf{SUS}\) of position \(k-1\). Their algorithm costs \(\mathcal{O}(occ)\) for reporting the \(\mathsf{SUS}\)s covering a particular location. By providing an efficient constant time algorithm for computing the shortest \(\mathsf{LSUS}\) covering each string position, they prove the following theorem.  
**Theorem 3**.: _All \(\mathsf{SUS}\)s corresponding to all the positions of string \(\mathcal{S}[1,n]\) can be computed in \(\mathcal{O}(n)\) time and space._  
For the implementation, they use _libdvsu/sort_ library for implementing the suffix array and \(\mathsf{lcp}\) array. They compare their results with [PERSON] et al.'s work and shows that, in terms of time complexity, both algorithms have almost the same processing time; however, their space usage is at least four times less for finding a single \(\mathsf{SUS}\) and two times less for finding all \(\mathsf{SUS}\)s.