# A Survey on Shortest Unique Substring Queries
## 4 Interval-SUS Queries
### Linear Time Approaches  
[PERSON] et al. [2] generalized Problem 1 to Problem 2 and presented a linear time and space data structure which can solve Problem 2 in \(\mathcal{O}(occ)\) time, where \(occ\) is the number of all \(\mathsf{SUS}\)s containing the query interval. The interval \(\mathsf{SUS}\) problem is more difficult to be solved in \(\mathcal{O}(occ)\) time, since there exist \(\Theta(n^{2})\) intervals and we cannot store the candidate answer for every possible interval. In order to deal with this issue, [PERSON] et al. use the concept of \(\mathsf{LS}\)s, \(\mathsf{RSUS}\), \(\mathsf{MUS}\), and Corollary 1 to prove Lemma 5.  
Corollary 1 ([34]): _There exists a data structure of \(\mathcal{O}(n)\) size which can be constructed in \(\mathcal{O}(n)\) time that can check whether a given substring of \(\mathcal{S}\) is unique in \(\mathcal{O}(1)\) time._  
Lemma 5 ([34]): _The answer of the interval-\(\mathsf{SUS}\) problem with the query interval \([x,y]\) must be the shortest of the following candidates:_  
1. \(\mathcal{S}[x,y]\) _if it is unique. This can be checked in constant time and linear space._
2. \(\mathsf{LSUS}(x)\)_: This can be computed in constant time using linear space by Lemma 4._
3. \(\mathsf{RSUS}(y)\)_: This can be computed in constant time using linear space by Lemma 4._
4. _The shortest_ \(\mathsf{MUS}\) _containing_ \([x,y]\)_: It remains to show their structure of computing this candidate._Let \(M\) be the set of all MUSs in \(\mathcal{S}\). For presenting their data structure, they define a set of intervals denoted by \(I\), such that \([i,j]\in I\) iff \(\mathcal{S}[i,j]\) is in \(M\). Then, they reduce the interval-SUS problem to _Containment Min_. Given an interval \([x,y]\), a containment min query returns the shortest interval in \(I\) which contains \([x,y]\). [PERSON] et al. [2] proposed a data structure of size \(\mathcal{O}(n)\) in which RMQ is performed to answer a containment min query in \(\mathcal{O}(1)\) time.  
In addition, they show how to report all SUSs in the case that interval SUS has more than one answer. For this purpose, they use an auxiliary problem which is defined below.  
**Position Constraint Query**. Given a substring \(\mathcal{S}[x,y]\) and two ranges \(range_{start}=[s_{1},s_{2}]\) and \(range_{end}=[e_{1},e_{2}]\) both in \([1,n]\), the problem is to return a unique substring \(\mathcal{S}[i,j]\) with the minimum length that contains \(\mathcal{S}[x,y]\) such that \(i\in[s_{1},s_{2}]\) and \(j\in[e_{1},e_{2}]\).  
This problem is a constraint version of the interval SUS problem where the starting and ending positions of the answer substring should be contained in the two intervals specified in the problem. They start with the normal interval-SUS query. Given the input interval \([x,y]\), let \(\mathcal{S}[i,j]\) be the answer of the interval-SUS. They consider two intervals \([1,i-1]\) and \([i+1,x]\). Now, using two position constraint queries, the next answers can be found. First, they run a position constrained query with \(\mathcal{S}[x,y]\), \(range_{start}=[1,i-1]\) and \(range_{end}=[y,n]\) to return the other possible answers. The other query corresponding to \([i+1,x]\) is symmetrical. In total, their algorithm takes \(\mathcal{O}(occ)\) time to report all the SUSs.  
The mentioned algorithms are in the RAM model. They also consider solving Problem 2 in the standard external memory model [35]. They follow a similar technique. Assume that \(\mathcal{O}(SORT(n))\) is the number of I/Os needed to sort \(n\) elements and \(B\) is the number of words in a block of a disk. They pre-compute an index structure from \(\mathcal{S}\) in \(\mathcal{O}(SORT(n))\) I/Os in external memory that occupies \(\mathcal{O}(n/B)\) blocks and can answer any shortest unique substring query in \(\mathcal{O}(1)\) I/Os [2].