# A Survey on Shortest Unique Substring Queries
## 7 Range-Sus  
Range queries are a classic data structure topic, which has a great motivation in string processing problems [5; 24; 25; 26]. In 2019, [PERSON] et al. [5] studied the local shortest unique substring which starts in a specific region or range of the string. Given a range \([\alpha,\beta]\), the problem is to return a shortest substring \(\mathcal{S}[k,k+h-1]\) of \(\mathcal{S}\) with exactly one occurrence in \([\alpha,\beta]\); i.e., \(k\in[\alpha,\beta]\), there is no \(k^{\prime}\in[\alpha,\beta]\) such that \(\mathcal{S}[k,k+h-1]=\mathcal{S}[k^{\prime},k^{\prime}+h-1]\), and \(h\) is minimal. [PERSON] et al. presented an \(\mathcal{O}(n\log n)\)-word data structure which answers \(\tau\)SUS queries in \(\mathcal{O}(\log_{w}n)\) time per query in the word RAM model, where \(w=\Omega(\log n)\) is the word size [5]. The _Range Shortest Unique Substring_ problem is formally defined as follows:  
Problem 6: \(\tau\)SUS Queries  
Preprocess: String \(\mathcal{S}[1,n]\).  
Query: Range \([\alpha,\beta]\), where \(1\leq\alpha\leq\beta\leq n\).  
Output: \((p,\ell)\) such that \(\mathcal{S}[p,p+\ell-1]\) is a shortest string with exactly one occurrence in \([\alpha,\beta]\).  
If \(\alpha=\beta\), the answer \((\alpha,1)\) is trivial. Thus, in the rest, we assume that \(\alpha<\beta\).  
Example 5 ([5]): _Given \(\mathcal{S}=\mathbf{caabcaddaacaddaaabac}\) and a query \([\alpha,\beta]=[5,16]\), we need to find a shortest substring of \(\mathcal{S}\) with exactly one occurrence in \([5,16]\). The output here is \((p,\ell)=(10,2)\) since \(\mathcal{S}[10,11]=\mathbf{ac}\) is the shortest substring of \(\mathcal{S}\) with exactly one occurrence in \([5,16]\)._  
For each position \(k\in[1,n]\), [PERSON] et al. [5] provide a data structure to keep track of the last and next occurrence of substring \(\mathcal{S}[k,k+h-1]\), denoted by \(\mathsf{Prev}(k,h)\) and \(\mathsf{Next}(k,h)\), respectively. They define \(\lambda(a,b,k)\) and \(C_{k}\) as follows:  
\[\lambda(a,b,k)=\min\{h\mid\mathsf{Prev}(k,h)<a\;\;\text{\bf and}\;\;\mathsf{ Next}(k,h)>b\}.\]  
\[C_{k}=\{h\mid(\mathsf{Next}(k,h),\mathsf{Prev}(k,h))\
eq(\mathsf{Next}(k,h-1), \mathsf{Prev}(k,h-1))\}.\]  
Their main result is providing an upper bound on the size of all \(C_{k}\)s, which is given in the following lemma.  
**Lemma 6** ([5]).: \(\sum_{k}|C_{k}|=\mathcal{O}(n\log n)\)__  
By the definition, \(\lambda(a,b,k)\) is the length of the shortest substring that starts at position \(k\), and \(C_{k}\) is the set of candidate length for the \(\mathsf{RSUS}\) answer, which starts at position \(k\).  
[PERSON] et al. solved \(\mathsf{rSUS}\) queries by reducing the problem to an top-\(1\) rectangle stabbing query on a set of rectangles with input point \((\alpha,\beta)\). Assume that the answer for Problem 6 is \((p,\ell)\). Given a query range \([\alpha,\beta]\), the answer \((p,\ell)\) we are looking for is the pair \((k,h)\) with the minimum \(h\) under the following conditions: \(k\in[\alpha,\beta]\), \(h\in C_{k}\), \(\mathsf{Prev}(k,h)<\alpha\) and \(\mathsf{Next}(k,h)>\beta\). Equivalently, \((p,\ell)\) is the pair \((k,h)\) with the minimum \(h\), such that \(h\in C_{k}\), \(\alpha\in(\mathsf{Prev}(k,h),k]\), and \(\beta\in[k,\mathsf{Next}(k,h))\).  
In the preprocessing step, they map each \(h\in C_{k}\) into a weighted rectangle \(R_{k,h}\) with weight \(h\) and defined as follows:  
\[R_{k,h}=[\mathsf{Prev}(k,h)+1,k]\times[k,\mathsf{Next}(k,h)-1].\]  
After query \([\alpha,\beta]\) comes, the lowest weighted rectangle which stabbed by the point \((\alpha,\beta)\) is \(R_{p,\ell}\). By combining the optimal data structure for top-\(1\) rectangle stabbing presented by [PERSON] et al. (2014) and the bound on the number of candidate lengths in Lemma 6, they prove the following result.  
**Theorem 12**.: _There exists an \(\mathcal{O}(n\log n)\)-word data structure which answers \(\mathsf{rSUS}\) queries in \(\mathcal{O}(\log_{w}n)\) time per query in the word RAM model, where \(w=\Omega(\log n)\) is the word size._