# Efficient Data Structures for Range Shortest Unique Substring Queries +
## 1 Introduction  
Finding regularities in strings is one of the main topics of combinatorial pattern matching and its applications [1]. Among the most well-studied types of string regularities is the notion of repeat. Let \(\mathsf{T}[1,n]\) be a string of length \(n\). A substring \(\mathsf{T}[i,j]\) of \(\mathsf{T}\) is called a repeat if it occurs more than once in \(\mathsf{T}\). The notion of unique substring is dual: it is a substring \(\mathsf{T}[i,j]\) of \(\mathsf{T}\) that does not occur more than once in \(\mathsf{T}\). Computing repeats and unique substrings has applications in computational biology [2, 3] and information retrieval [4, 5].  
In this paper, we are interested in the notion of shortest unique substring. All of the shortest unique substrings of string \(\mathsf{T}\) can be computed in \(\mathcal{O}(n)\) time using the suffix tree data structure [6, 7]. Many different problems based on this notion have already been studied. [PERSON] et al. [4] considered the following problem on the so-called position (or point) queries. Given a position \(i\) of \(\mathsf{T}\), return a shortest unique substring of \(\mathsf{T}\) covering \(i\). The authors gave an \(\mathcal{O}(n^{2})\)-time and \(\mathcal{O}(n)\)-space algorithm, which finds the shortest unique substring covering every position of \(\mathsf{T}\). Since then, the problem hasbeen revisited and optimal \(\mathcal{O}(n)\)-time algorithms have been presented by [PERSON] et al. [8] and [PERSON] et al. [9]. Several other variants of this problem have been investigated [10; 11; 12; 13; 14; 15; 16; 17; 18; 19].  
We introduce a natural generalization of the shortest unique substring problem. Specifically, our focus is on the range version of the problem, which we call the Range Shortest Unique Substring (rSUS) problem. The task is to construct a data structure over \(\mathsf{T}\) to be able to answer the following type of online queries efficiently. Given a range \([\alpha,\beta]\), return a shortest substring \(\mathsf{T}[k,k+h-1]\) of \(\mathsf{T}\) with exactly one occurrence (starting position) in \([\alpha,\beta]\); i.e., \(k\in[\alpha,\beta]\), there is no \(k^{\prime}\in[\alpha,\beta]\ (k^{\prime}\
eq k)\), such that \(\mathsf{T}[k,k+h-1]=\mathsf{T}[k^{\prime},k^{\prime}+h-1]\), and \(h\) is minimal. Note that this substring, \(\mathsf{T}[k,k+h-1]\), may end at a position \(k+h-1>\beta\). Further note that there may be multiple shortest unique substrings.  
Range queries are a classic data structure topic [20; 21; 22]. A range query \(q=f(A,i,j)\) on an array of \(n\) elements over some set \(S\), denoted by \(A[1,n]\), takes two indices \(1\leq i\leq j\leq n\), a function \(f\) defined over arrays of elements of \(S\), and outputs \(f(A[i,j])=f(A[i],\ldots,A[j])\). Range query data structures have also been specifically considered for strings [23; 24; 25; 26]. For instance, in bioinformatics applications we are often interested in finding regularities in certain regions of a DNA sequence [27; 28; 29; 30; 31]. In the Range-LCP problem, defined by [PERSON] et al. [23], the task is to construct a data structure over \(\mathsf{T}\) to be able to answer the following type of online queries efficiently. Given a range \([\alpha,\beta]\), return \(i,j\in[\alpha,\beta]\) such that the length of the longest common prefix of \(\mathsf{T}[i,n]\) and \(\mathsf{T}[j,n]\) is maximal among all pairs of suffixes within this range. The state of the art is an \(\mathcal{O}(n)\)-word data structure supporting \(\mathcal{O}(\log^{\mathcal{O}(1)}n)\)-time (polylogarithmic-time) queries [25] (see also [26; 32]).