# A Survey on Shortest Unique Substring Queries
## 4 Interval-SUS Queries
### RLE-Based Approaches  
The _Run Length Encoding (RLE)_ of a string is a compressed representation in which each maximal run of a character \(c\) of length \(\ell\) is encoded as \(c^{\ell}\). For instance, the \(RLE\) of string _aaaaaaabbbbaac_ is \(a^{\prime}b^{4}a^{3}c^{1}\). [PERSON] et al. [8] considered solving Problem 2 in the case where the input string is given in \(RLE\) representation. Their motivation was to reduce space and time complexity of processing the input string. They presented a data structure of size \(\mathcal{O}(m+\pi_{s}(N,m))\) that can be constructed in \(\mathcal{O}(m\log m+\pi_{c}(N,m))\) time to answer interval-SUS queries in \(\mathcal{O}(\pi_{q}(N,m)+occ)\) time, where \(occ\) is the output size, and \(\pi_{s}(N,m)\), \(\pi_{c}(N,m)\) and \(\pi_{q}(N,m)\) are the size, construction time and the query time for a predecessor/successor query on \(m\) elements from a universe of \([1,N]\). In their approach, they use combinatorial properties on MUSs and \(RLE\) strings. Let \(m\) be the length of the string \(\mathcal{S}\) in \(RLE\) representation. We denote \(RLE\) representation of \(\mathcal{S}\) by \(RLE(\mathcal{S})\). They show that the number of MUSs in \(RLE(\mathcal{S})\) is \(2m-1\). Thus, instead of dealing with \(\Theta(n)\) MUSs like the previous related results, a considerable amount of space and time would be reduced if there exist runs in the string. By doing so, they were able to build an \(\mathcal{O}(m)\) size data structure for the \(RLE\) version of SUS problem, which is formally defined as follows:  
**Problem 3**. : _RLE-_SUS _Queries_  
_Preprocess:_ \(RLE(\mathcal{S})=\epsilon_{1}^{\ell_{1}}\epsilon_{2}^{\ell_{2}}\cdots\epsilon _{m}^{\ell_{m}}\)  
_Query: An interval \([s,t]\in[1,n]\)  
_Return: All SUS of \(\mathcal{S}\) containing the query interval \([s,t]\)_  
For solving Problem 3, they show how to precompute all the MUSs using a specific type of suffix arrays for \(RLE\) strings [36]. Before discussing their techniques, we bring some definitions. Let \(bpos(i)\), \(epos(i)\) and \(exp(i)\) be the beginning position, ending position, and exponent of the ith run of \(RLE(\mathcal{S})\). Let \(P\) be be any subset of positions of \(\mathcal{S}\). The sparse suffix array of \(\mathcal{S}\) w.r.t \(P\) denoted by \(\textsf{SSA}_{P}\) is an array of size \(|P|\) such that \(\mathsf{SSA}_{P}[i]\in P\) for all \(1\leq i\leq|P|\) and also like a normal suffix array \(\mathsf{SSA}_{P}[i]\) is lexicographically smaller than \(\mathsf{SSA}_{P}[i+1]\). They use _trancated_\(RLE\)_suffix array_ for \(RLE(\mathcal{S})\) denoted by \(tRLESA\), in which \(P\) is the set of \(\mathit{eps}(i)\) for \(1\leq i\leq m\). In addition, let \(EXP\) be an array of length \(m\) such that \(EXP[i]=exp(k)\), where \(tRLESA[i]=\mathit{eps}(k)\). Given \(RLE(s)\), all the defined arrays can be computed in \(\mathcal{O}(m\log m)\) time with \(\mathcal{O}(m)\) working space [14]. In order to compute \(\mathsf{MUS}\)s from \(RLE(\mathcal{S})\), they consider three disjoint partitions of \(\mathsf{MUS}\), \(M_{1},M_{2},M_{3}\). The first partition consists of \(\mathsf{MUS}\)s which are contained in runs. The second one is \(\mathsf{MUS}\)s that start at the last characters of runs, and all the other \(\mathsf{MUS}\)s considered to be in the third partitions. By the fact that each \(\mathsf{MUS}\) cannot be a proper substring of another \(\mathsf{MUS}\) and discussing the size of each partition separately, they prove that \(|M|\leq 2m-1\). Then, they show how to find \(\mathsf{MUS}\) in \(\mathcal{O}(m\log m)\) time and \(\mathcal{O}(m)\) space, by computing the partitions. In order to compute \(M_{1}\), for each character used in \(\mathcal{S}\), they check whether there exists a run of that character with a unique maximum exponent, since the number of distinct character used in \(\mathcal{S}\) is \(\leq m\), this procedure can be done in \(\mathcal{O}(m\log m)\) time and \(\mathcal{O}(m)\) space using a sorting algorithm.