Efficient Data Structures for Range Shortest Unique Substring Queries ^†

Abstract

Let $\mathsf{T}[1,n]$ be a string of length n and $\mathsf{T}[i,j]$ be the substring of $\mathsf{T}$ starting at position i and ending at position j. A substring $\mathsf{T}[i,j]$ of $\mathsf{T}$ is a repeat if it occurs more than once in $\mathsf{T}$; otherwise, it is a unique substring of $\mathsf{T}$. Repeats and unique substrings are of great interest in computational biology and information retrieval. Given string $\mathsf{T}$ as input, the Shortest Unique Substring problem is to find a shortest substring of $\mathsf{T}$ that does not occur elsewhere in $\mathsf{T}$. In this paper, we introduce the range variant of this problem, which we call the Range Shortest Unique Substring problem. The task is to construct a data structure over $\mathsf{T}$ answering the following type of online queries efficiently. Given a range $[\alpha ,\beta ]$, return a shortest substring $\mathsf{T}[i,j]$ of $\mathsf{T}$ with exactly one occurrence in $[\alpha ,\beta ]$. We present an $\mathcal{O}(nlogn)$-word data structure with $\mathcal{O}\left({log}_{w}n\right)$ query time, where $w=\Omega (logn)$ is the word size. Our construction is based on a non-trivial reduction allowing for us to apply a recently introduced optimal geometric data structure [Chan et al., ICALP 2018]. Additionally, we present an $\mathcal{O}\left(n\right)$-word data structure with $\mathcal{O}\left(\sqrt{n}{log}^{ϵ}n\right)$ query time, where $ϵ>0$ is an arbitrarily small constant. The latter data structure relies heavily on another geometric data structure [Nekrich and Navarro, SWAT 2012].

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}\left(n\right)$ time using the suffix tree data structure [6,7]. Many different problems based on this notion have already been studied. Pei 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}\left(n^2\right)$-time and $\mathcal{O}\left(n\right)$-space algorithm, which finds the shortest unique substring covering every position of $\mathsf{T}$. Since then, the problem has been revisited and optimal $\mathcal{O}\left(n\right)$-time algorithms have been presented by Ileri et al. [8] and Tsuruta 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 ($\mathsf{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 }\ne 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\le i\le j\le n$, a function f defined over arrays of elements of S, and outputs $f\left(A\right[i,j\left]\right)=f\left(A\right[i],\dots ,A[j\left]\right)$. 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 Amir 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}\left(n\right)$-word data structure supporting $\mathcal{O}\left({log}^{\mathcal{O}\left(1\right)}n\right)$-time (polylogarithmic-time) queries [25] (see also [26,32]).

1.1. Main Problem and Main Results

An alphabet $\Sigma$ is a finite nonempty set of elements called letters. We fix a string $\mathsf{T}[1,n]=\mathsf{T}\left[1\right]\cdots \mathsf{T}\left[n\right]$ over $\Sigma$. The length of $\mathsf{T}$ is denoted by $\left|\mathsf{T}\right|=n$. By $\mathsf{T}[i,j]=\mathsf{T}\left[i\right]\cdots \mathsf{T}\left[j\right]$, we denote the substring of $\mathsf{T}$ starting at position i and ending at position j of $\mathsf{T}$. We say that another string $\mathsf{P}$ has an occurrence in $\mathsf{T}$ or, more simply, that $\mathsf{P}$ occurs in $\mathsf{T}$ if $\mathsf{P}=\mathsf{T}[i,i+|\mathsf{P}|-1]$, for some i. Thus, we characterize an occurrence of $\mathsf{P}$ by its starting position i in $\mathsf{T}$. A prefix of $\mathsf{T}$ is a substring of $\mathsf{T}$ of the form $\mathsf{T}[1,i]$ and a suffix of $\mathsf{T}$ is a substring of $\mathsf{T}$ of the form $\mathsf{T}[i,n]$.

We next formally define the main problem considered in this paper.

• Problem $\mathsf{rSUS}$
• Preprocess: String $\mathsf{T}[1,n]$.
• Query: Range $[\alpha ,\beta ]$, where $1\le \alpha \le \beta \le n$.
• Output:$(p,\ell )$ such that $\mathsf{T}[p,p+\ell -1]$ is a shortest string with exactly one occurrence in $[\alpha ,\beta ]$.

If $\alpha =\beta$ the answer $(\alpha ,1)$ is trivial. So, in the rest we assume that $\alpha <\beta$.

Example 1.

Given $\mathsf{T}=\stackrel{\mathit{1}}{\mathit{c}}\stackrel{\mathit{2}}{\mathit{a}}\stackrel{\mathit{3}}{\mathit{a}}\stackrel{\mathit{4}}{\mathit{b}}\stackrel{\mathit{5}}{\mathit{c}}\stackrel{\mathit{6}}{\mathit{a}}\stackrel{\mathit{7}}{\mathit{d}}\stackrel{\mathit{8}}{\mathit{d}}\stackrel{\mathit{9}}{\mathit{a}}\stackrel{\mathit{10}}{\mathit{a}}\stackrel{\mathit{11}}{\mathit{c}}\stackrel{\mathit{12}}{\mathit{a}}\stackrel{\mathit{13}}{\mathit{d}}\stackrel{\mathit{14}}{\mathit{d}}\stackrel{\mathit{15}}{\mathit{a}}\stackrel{\mathit{16}}{\mathit{a}}\stackrel{\mathit{17}}{\mathit{a}}\stackrel{\mathit{18}}{\mathit{a}}\stackrel{\mathit{19}}{\mathit{b}}\stackrel{\mathit{20}}{\mathit{a}}\stackrel{\mathit{21}}{\mathit{c}}$ and a query $[\alpha ,\beta ]=[5,16]$, we need to find a shortest substring of $\mathsf{T}$ with exactly one occurrence in $[5,16]$. The output here is $(p,\ell )=(10,2)$, because $\mathsf{T}[10,11]=\mathbf{ac}$ is the shortest substring of $\mathsf{T}$ with exactly one occurrence in $[5,16]$.

Our main results are summarized below. We consider the standard word-RAM model of computations with w-bit machine words, where $w=\Omega (logn)$, for stating our results.

Theorem 1.

We can construct an $\mathcal{O}(nlogn)$-word data structure that can answer any $\mathsf{rSUS}$ query on $T[1,n]$ in $\mathcal{O}\left({log}_{w}n\right)$ time.

Theorem 2.

We can construct an $\mathcal{O}\left(n\right)$-word data structure that can answer any $\mathsf{rSUS}$ query on $T[1,n]$ in $\mathcal{O}\left(\sqrt{n}{log}^{ϵ}n\right)$ time, where $ϵ>0$ is an arbitrarily small constant.

1.2. Paper Organization

In Section 2, we prove Theorem 1 and, in Section 3, we prove Theorem 2. We conclude this paper in Section 4 with some future proposals. An early version of this paper appeared as [33]. When compared to that early version ([33]), Theorem 2 is new.

2. An $\mathcal{O}(\mathit{n}log\mathit{n})$-Word Data Structure

Our construction is based on ingredients, such as the suffix tree [7], heavy-light decomposition [34], and a geometric data structure for rectangle stabbing [35]. Let us start with some definitions.

Definition 1.

For a position $k\in [1,n]$ and $h\ge 1$, we define $\mathsf{Prev}(k,h)$ and $\mathsf{Next}(k,h)$, as follows:

$$\mathsf{Prev}(k,h)=\underset{j}{max}\{\{j<k\mid \mathsf{T}[k,k+h-1]=\mathsf{T}[j,j+h-1]\}\cup \{-\infty \}\}$$

$$\mathsf{Next}(k,h)=\underset{j}{min}\{\{j>k\mid \mathsf{T}[k,k+h-1]=\mathsf{T}[j,j+h-1]\}\cup \{+\infty \}\}.$$

Intuitively, let x and y be the occurrences of $\mathsf{T}[k,k+h-1]$ right before and right after the position k, respectively. Subsequently, $\mathsf{Prev}(k,h)=x$ and $\mathsf{Next}(k,h)=y$. If x (resp., y) does not exist, then $\mathsf{Prev}(k,h)=-\infty$ (resp., $\mathsf{Next}(k,h)=+\infty$).

Definition 2.

Let $k\in [a,b]$. We define $\lambda (a,b,k)$, as follows:

$$\lambda (a,b,k)=min\{h\mid \mathsf{Prev}(k,h)<a\mathbf{and}\mathsf{Next}(k,h)>b\}.$$

Intuitively, $\lambda (a,b,k)$ denotes the length of the shortest substring that starts at position k with exactly one occurrence in $[a,b]$.

Definition 3.

For a position $k\in [1,n]$, we define $C_k$, as follows:

$$C_k=\{h>1\mid (\mathsf{Next}(k,h),\mathsf{Prev}(k,h))\ne (\mathsf{Next}(k,h-1),\mathsf{Prev}(k,h-1))\}\cup \left\{1\right\}$$

Example 2.(Running Example for Definition 3) Let $\mathsf{T}=\stackrel{\mathit{1}}{\mathit{c}}\stackrel{\mathit{2}}{\mathit{a}}\stackrel{\mathit{3}}{\mathit{a}}\stackrel{\mathit{4}}{\mathit{b}}\stackrel{\mathit{5}}{\mathit{c}}\stackrel{\mathit{6}}{\mathit{a}}\stackrel{\mathit{7}}{\mathit{d}}\stackrel{\mathit{8}}{\mathit{d}}\stackrel{\mathit{9}}{\mathit{a}}\stackrel{\mathit{10}}{\mathit{a}}\stackrel{\mathit{11}}{\mathit{c}}\stackrel{\mathit{12}}{\mathit{a}}\stackrel{\mathit{13}}{\mathit{d}}\stackrel{\mathit{14}}{\mathit{d}}\stackrel{\mathit{15}}{\mathit{a}}\stackrel{\mathit{16}}{\mathit{a}}\stackrel{\mathit{17}}{\mathit{a}}\stackrel{\mathit{18}}{\mathit{a}}\stackrel{\mathit{19}}{\mathit{b}}\stackrel{\mathit{20}}{\mathit{a}}\stackrel{\mathit{21}}{\mathit{c}}$ and $k=10$. We have that $\left(\mathsf{Next}\right(10,1),\mathsf{Prev}(10,1\left)\right)=(12,9)$, $\left(\mathsf{Next}\right(10,2),\mathsf{Prev}(10,2\left)\right)=(20,-\infty )$, and $\left(\mathsf{Next}\right(10,3),\mathsf{Prev}(10,3\left)\right)=(+\infty ,-\infty )$. Thus, $C_{10}=\{2,3\}\cup \left\{1\right\}=\{1,2,3\}$.

Intuitively, $C_k$ stores the set of candidate lengths for the shortest unique substrings starting at position k. We make the following observation.

Observation 1.

$\lambda (a,b,k)\in C_k$, for any $1\le a\le b\le n$.

Example 3.(Running Example for Observation 1) Let $\mathsf{T}=\stackrel{\mathit{1}}{\mathit{c}}\stackrel{\mathit{2}}{\mathit{a}}\stackrel{\mathit{3}}{\mathit{a}}\stackrel{\mathit{4}}{\mathit{b}}\stackrel{\mathit{5}}{\mathit{c}}\stackrel{\mathit{6}}{\mathit{a}}\stackrel{\mathit{7}}{\mathit{d}}\stackrel{\mathit{8}}{\mathit{d}}\stackrel{\mathit{9}}{\mathit{a}}\stackrel{\mathit{10}}{\mathit{a}}\stackrel{\mathit{11}}{\mathit{c}}\stackrel{\mathit{12}}{\mathit{a}}\stackrel{\mathit{13}}{\mathit{d}}\stackrel{\mathit{14}}{\mathit{d}}\stackrel{\mathit{15}}{\mathit{a}}\stackrel{\mathit{16}}{\mathit{a}}\stackrel{\mathit{17}}{\mathit{a}}\stackrel{\mathit{18}}{\mathit{a}}\stackrel{\mathit{19}}{\mathit{b}}\stackrel{\mathit{20}}{\mathit{a}}\stackrel{\mathit{21}}{\mathit{c}}$ and $k=10$. We have that $C_{10}=\{1,2,3\}$. For $a=5$ and $b=16$, $\lambda (5,16,10)=2$, denoting substring $\mathbf{ac}$. For $a=5$ and $b=20$, $\lambda (5,20,10)=3$, denoting substring $\mathit{a}\mathit{c}\mathit{a}$.

The following combinatorial lemma is crucial for efficiency.

Lemma 1.

${\sum }_k\left|C_k\right|=\mathcal{O}(nlogn)$.

Proof. 

The proof of Lemma 1 is deferred to Section 2.1. ☐

We are now ready to present our construction. By Observation 1, for a given query range $[\alpha ,\beta ]$, the answer $(p,\ell )$ that 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 \left(\mathsf{Prev}\right(k,h),k]$, and $\beta \in [k,\mathsf{Next}(k,h\left)\right)$. We map each $h\in C_k$ into a weighted rectangle $R_{k,h}$ with weight h, which is defined as follows:

$$R_{k,h}=[\mathsf{Prev}(k,h)+1,k]\times [k,\mathsf{Next}(k,h)-1].$$

Let $\mathcal{R}$ be the set of all such rectangles, then the lowest weighted rectangle in $\mathcal{R}$ stabbed by the point $(\alpha ,\beta )$ is $R_{p,\ell }$. In short, an $\mathsf{rSUS}$ query on $\mathsf{T}[1,n]$ with an input range $[\alpha ,\beta ]$ can be reduced to an equivalent top-1 rectangle stabbing query on a set $\mathcal{R}$ of rectangles with input point $(\alpha ,\beta )$. In the 2-d Top-1 Rectangle Stabbing problem, we preprocess a set of weighted rectangles in 2-d, so that given a query point q the task is to report the largest (or lowest) weighted rectangles containing q [35]. Similarly, here, the task is to report the lowest weighted rectangle in $\mathcal{R}$ containing the point $(\alpha ,\beta )$ (see Figure 1 for an illustration). By Lemma 1, we have that $\left|\mathcal{R}\right|=\mathcal{O}(nlogn)$. Therefore, by employing the optimal data structure for top-1 rectangle stabbing presented by Chan et al. [35], which takes $\mathcal{O}\left(\right|\mathcal{R}\left|\right)$-word space supporting $\mathcal{O}\left({log}_w\right|\mathcal{R}\left|\right)$-time queries, we arrive at the space-time trade-off of Theorem 1. This completes our construction.

2.1. Proof of Lemma 1

Let $\mathsf{lcp}(i,j)$ denote the length of the longest common prefix of the suffixes of $\mathsf{T}$ starting at positions i and j in $\mathsf{T}$. Additionally, let S denote the set of all $(x,y)$ pairs, such that $1\le x<y\le n$ and $\mathsf{lcp}(x,y)>\mathsf{lcp}(x,z)$, for all $z\in [x+1,y-1]$. The proof can be broken down into Lemma 2 and Lemma 3.

Lemma 2.

${\sum }_k|C_k|=\mathcal{O}(\left|S\right|)$.

Proof. 

Let us fix a position k. Let

$$C_k^{\prime }=\{h>1\mid \mathsf{Prev}(k,h)\ne \mathsf{Prev}(k,h-1)\}$$

$$C_k^{″}=\{h>1\mid \mathsf{Next}(k,h)\ne \mathsf{Next}(k,h-1)\}.$$

Clearly we have that $C_k=C_k^{\prime }\cup C_k^{″}\cup \left\{1\right\}$.

The following statements can be deduced by a simple contradiction argument:

• Let $i=\mathsf{Prev}(k,h)\ne -\infty$, where $h\in C_k^{\prime }$, then $i=\mathsf{Prev}(k,\mathsf{lcp}(i,k\left)\right)$
• Let $j=\mathsf{Next}(k,h)\ne \infty$, where $h\in C_k^{″}$, then $j=\mathsf{Next}(k,\mathsf{lcp}(k,j\left)\right)$.

Figure 2 illustrates the proof for the first statement. The second one can be proved in a similar fashion.

Clearly, $|C_k^{\prime }|$ is proportional to the number of $(i,k)$ pairs, such that $\mathsf{lcp}(i,k)\ne 0$ and $i=\mathsf{Prev}(k,\mathsf{lcp}(i,k\left)\right)$. Similarly, $|C_k^{″}|$ is proportional to the number of $(k,j)$ pairs, such that $\mathsf{lcp}(k,j)\ne 0$ and $j=\mathsf{Next}(k,\mathsf{lcp}(k,j\left)\right)$. Therefore, ${\sum }_k\left|C_k\right|$ is proportional to the number of $(x,y)$ pairs, such that $\mathsf{lcp}(x,y)\ne 0$ and $\mathsf{lcp}(x,y)>\mathsf{lcp}(x,z)$, for all $z\in [x+1,y-1]$. This completes the proof of Lemma 2.  ☐

Lemma 3.

$\left|S\right|=\mathcal{O}(nlogn)$.

Proof. 

Consider the suffix tree data structure of string $\mathsf{T}[1,n]$, which is a compact trie of the n suffixes of $\mathsf{T}$ appended with a letter $\$\notin \Sigma$ [7]. This suffix tree consists of $n+1$ leaves (one for each suffix of $\mathsf{T}$) and at most n internal nodes. The edges are labeled with substrings of $\mathsf{T}$. Let u be the lowest common ancestor of the leaves corresponding to the strings $\mathsf{T}[x,n]\$$ and $\mathsf{T}[y,n]\$$. Subsequently, the concatenation of the edge labels on the path from the root to u is exactly the longest common prefix of $\mathsf{T}[x,n]\$$ and $\mathsf{T}[y,n]\$$. For any node u, we denote, by $\mathsf{size}\left(u\right)$, the total number of leaf nodes of the subtree rooted at u.

We decompose the nodes in the suffix tree into light and heavy nodes. The root node is light and for any internal node, exactly one child is heavy. Specifically, the heavy child is the one having the largest number of leaves in its subtree (ties are broken arbitrarily). All other children are light. This tree decomposition is known as heavy-light decomposition. We have the following critical observation. Any path from the root to a leaf node contains many nodes; however, the number of light nodes is at most $logn$ [34,36]. Additionally, corresponding to the $n+1$ leaves of the suffix tree, there are $n+1$ paths from the root to the leaves. Therefore, the sum of subtree sizes over all light nodes is $\mathcal{O}(nlogn)$.

We are now ready to complete the proof. Let $S_u\subseteq S$ denote the set of pairs $(x,y)$, such that the lowest common ancestor of the leaves corresponding to suffixes $\mathsf{T}[x,n]\$$ and $\mathsf{T}[y,n]\$$ is u. Clearly, the paths from the root to the leaves that correspond to suffixes $\mathsf{T}[x,n]\$$ and $\mathsf{T}[y,n]\$$ pass from two distinct children of node u and then at least one of the two must be a light node. There are two cases. In the first case, both leaves are under the light children. In the second case, one leaf is under a light child and the other is under the heavy child. In both cases, we have at least one leaf under a light node. If we fix the leaf that is under the light node, we can enumerate the total number of pairs based on the subtree size of the light nodes. Therefore, $|S_u|$ is at most twice the sum of $\mathsf{size}(·)$ over all light children of u. Since $\left|S\right|={\sum }_u\left|S_u\right|$, we can bound $\left|S\right|$ by the sum of $\mathsf{size}(·)$ over all light nodes in the suffix tree, which is $\mathcal{O}(nlogn)$. This completes the proof of Lemma 3.  ☐

3. An $\mathcal{O}\left(\mathit{n}\right)$-Word Data Structure

This section is dedicated to proving Theorem 2. For simplicity, we only focus on the computation of the length ℓ of the output $(p,\ell )$.

Let $\mathsf{SA}$ be the suffix array of string $\mathsf{T}$ of length n, which is a permutation of $\{1,\cdots ,n\}$, such that $\mathsf{SA}\left[i\right]=j$ if $\mathsf{T}[j,n]$ is the ith lexicographically smallest suffix of $\mathsf{T}$ [37]. Further, let ${\mathsf{SA}}^{-1}$ be the inverse suffix array of string $\mathsf{T}$ of length n, which is a permutation of $\{1,\cdots ,n\}$, such that ${\mathsf{SA}}^{-1}\left[\mathsf{SA}\left[i\right]\right]=i$. Moreover, $\mathsf{SA}$ of $\mathsf{T}$ can be constructed in linear time and space [38,39].

We observe that an $\mathcal{O}(\beta -\alpha +1)$-time solution is straightforward with the aid of the suffix tree of $\mathsf{T}$ as follows. First, identify those leaves corresponding to the suffixes starting within $[\alpha ,\beta ]$ using the inverse suffix array of $\mathsf{T}$ and mark them. Subsequently, for each marked leaf, identify its lowest ancestor node (and double mark it), such that a marked neighbor is also under it. This can be done via at most two $\mathcal{O}\left(1\right)$-time Lowest Common Ancestor (LCA) queries over the suffix tree of $\mathsf{T}$ while using $\mathcal{O}\left(n\right)$ additional space [22]. Afterwards, find the minimum over the string-depth of all double-marked nodes, add 1 to it, and report it as the length ℓ. The correctness is readily verified.

We employ the above procedure when $\beta -\alpha +1<3\Delta$, where $\Delta$ is a parameter to be set later. We now consider the case when $\beta -\alpha +1\ge 3\Delta$. Note that ℓ is the smallest element in $S^{*}=\{\lambda (\alpha ,\beta ,k)\mid k\in [\alpha ,\beta ]\}$. Let ${\alpha }^{\prime }$ be the smallest number after $\alpha$ and ${\beta }^{\prime }$ be the largest number before $\beta$, such that ${\alpha }^{\prime }$ and ${\beta }^{\prime }$ are multiples of $\Delta$. Subsequently, $S^{*}$ can be written as the union of $S^{\prime }=\{\lambda (\alpha ,\beta ,k)\mid k\in [\alpha ,{\alpha }^{\prime }-1]\cup [{\beta }^{\prime }+1,\beta ]\}$ and $S^{″}=\{\lambda (\alpha ,\beta ,k)\mid k\in [{\alpha }^{\prime },{\beta }^{\prime }]\}$. Furthermore, $S^{″}$ can be written as $S_1^{″}\cup S_2^{″}\cup S_3^{″}$, where

• $S_1^{″}=\{h=\lambda (\alpha ,\beta ,k)\mid k\in [{\alpha }^{\prime },{\beta }^{\prime }],\mathsf{Prev}(k,h)\in [{\alpha }^{\prime }-\Delta ,\alpha -1]\}$
• $S_2^{″}=\{h=\lambda (\alpha ,\beta ,k)\mid k\in [{\alpha }^{\prime },{\beta }^{\prime }],\mathsf{Next}(k,h)\in [\beta +1,{\beta }^{\prime }+\Delta ]\}$
• $S_3^{″}=\{h=\lambda (\alpha ,\beta ,k)\mid k\in [{\alpha }^{\prime },{\beta }^{\prime }],\mathsf{Prev}(k,h)\in (-\infty ,{\alpha }^{\prime }-\Delta -1],\mathsf{Next}(k,h)\in [{\beta }^{\prime }+\Delta +1,\infty )\}.$

Our construction is based on a solution to the Orthogonal Range Predecessor/Successor in 2-d problem. A set $\mathcal{P}$ of n points in an $[1,n]\times [1,n]$ grid can be preprocessed into a linear-space data structure, such that the following queries can be answered in $\mathcal{O}\left({log}^{ϵ}n\right)$ time per query [40]:

• $\mathsf{ORQ}([x^{\prime },x^{″}],[-\infty ,y^{″}])=arg{max}_j\{(i,j)\in \mathcal{P}\cap [x^{\prime },x^{″}]\times [-\infty ,y^{″}]\}$
• $\mathsf{ORQ}([-\infty ,x^{″}],[y^{\prime },y^{″}])=arg{max}_i\{(i,j)\in \mathcal{P}\cap [-\infty ,x^{″}]\times [y^{\prime },y^{″}]\}$
• $\mathsf{ORQ}([x^{\prime },x^{″}],[y^{\prime },+\infty ])=arg{min}_j\{(i,j)\in \mathcal{P}\cap [x^{\prime },x^{″}]\times [y^{\prime },+\infty ]\}$
• $\mathsf{ORQ}([x^{\prime },+\infty ],[y^{\prime },y^{″}])=arg{min}_i\{(i,j)\in \mathcal{P}\cap [x^{\prime },+\infty ]\times [y^{\prime },y^{″}]\}$.

We next show how to maintain additional structures, so that the smallest element in each of the above sets can be efficiently computed and, thus, the smallest among them can be reported as ℓ.

• Computing the Smallest Element in $S^{\prime }$: for each $k\in [\alpha ,{\alpha }^{\prime }-1]\cup [{\beta }^{\prime }+1,\beta ]$, we compute $\lambda (\alpha ,\beta ,k)$ and report the smallest among them. We handle each $\lambda (\alpha ,\beta ,k)$ query in time $\mathcal{O}\left({log}^{ϵ}n\right)$, as follows: first find the leaf corresponding to the string position k in the suffix tree of $\mathsf{T}$, then the last (resp., first) leaf on its left (resp., right) side, such that the string position x (resp., y) corresponding to it is in $[\alpha ,\beta ]$, and report $1+max\left\{\mathsf{lcp}\right(k,x),\mathsf{lcp}(k,y\left)\right\}$. To efficiently enable the computation of x (resp., y), we preprocess the suffix array into an $\mathcal{O}\left(n\right)$-word data structure that can answer orthogonal range predecessor (resp., successor) queries in $\mathcal{O}\left({log}^{ϵ}n\right)$ time [40].
• Computing the Smallest Element in $S_1^{″}$: for each $r\in [{\alpha }^{\prime }-\Delta ,\alpha -1]$, we compute the smallest element in $\{h=\lambda (\alpha ,\beta ,k)\mid k\in [{\alpha }^{\prime },{\beta }^{\prime }],\mathsf{Prev}(k,h)=r\}$ and report the smallest among them. The procedure is the following: find the leaf corresponding to the string position r in the suffix tree of $\mathsf{T}$ and the last (resp., first) leaf on its left (resp., right) side, such that its corresponding string position x (resp., y) is in $[{\alpha }^{\prime },{\beta }^{\prime }]$ (via orthogonal range successor/predecessor queries as earlier). Subsequently, $t=max\left\{\mathsf{lcp}\right(r,x),\mathsf{lcp}(r,y\left)\right\}$ is the length of the longest prefix of $\mathsf{T}[r,n]$ with an occurrence d in $[{\alpha }^{\prime },{\beta }^{\prime }]$. However, we need to verify whether occurrence d is unique and its $\mathsf{Prev}(d,t)=r$. For this, find the two leftmost occurrences of $\mathsf{T}[r,r+t-1]$ after r, denoted by $x^{\prime }$ and $y^{\prime }$ ($x^{\prime }<y^{\prime }$), via two orthogonal range successor queries. If $y^{\prime }$ does not exist, set $y^{\prime }=+\infty$. Then report $\lambda (\alpha ,\beta ,d)$ if ${\alpha }^{\prime }\le x^{\prime }\le {\beta }^{\prime }<y^{\prime }$. Otherwise, report $+\infty$.
• Computing the Smallest Element in $S_2^{″}$: for each $r\in [\beta +1,{\beta }^{\prime }+\Delta ]$, we compute the smallest element in $\{h=\lambda (\alpha ,\beta ,k)\mid k\in [{\alpha }^{\prime },{\beta }^{\prime }],\mathsf{Next}(k,h)=r\}$ and report the smallest among them. The procedure is analogous to that of $S_1^{″}$; i.e., find the length t of the longest prefix of $\mathsf{T}[r,n]$ with an occurrence d in $[{\alpha }^{\prime },{\beta }^{\prime }]$. Then, find the two rightmost occurrences of $\mathsf{T}[r,r+t-1]$ before r, denoted by $x^{\prime }$ and $y^{\prime }$ ($x^{\prime }<y^{\prime }$), via two orthogonal range successor queries. If $x^{\prime }$ does not exist, set $x^{\prime }=+\infty$. Subsequently, report $\lambda (\alpha ,\beta ,d)$ if $x^{\prime }<{\alpha }^{\prime }\le y^{\prime }\le {\beta }^{\prime }$. Otherwise, report $+\infty$.
• Computing the Smallest Element in $S_3^{″}$: the set $S_3^{″}$ can be written as $\{\lambda ({\alpha }^{\prime }-\Delta ,{\beta }^{\prime }+\Delta ,k)\mid k\in [{\alpha }^{\prime },{\beta }^{\prime }]\}$, which is now dependent only on ${\alpha }^{\prime },{\beta }^{\prime }$ and $\Delta$. Therefore, our idea is to pre-compute and explicitly store the minimum element in $\left\{\lambda \right(a-\Delta ,b+\Delta ,k)\mid k\in [a,b\left]\right\}$ for all $(a,b)$ pairs, where both a and b are multiples of $\Delta$, and for that the desired answer can be retrieved in constant time. The additional space needed is $\mathcal{O}\left({(n/\Delta )}^2\right)$.

We set $\Delta =\lfloor \sqrt{n}\rfloor$. The total space is then $\mathcal{O}\left(n\right)$ and total time is $\mathcal{O}(\Delta {log}^{ϵ}n)=\mathcal{O}\left(\sqrt{n}{log}^{ϵ}n\right)$. Therefore, we arrive at Theorem 2.

4. Final Remarks

We introduced the Range Shortest Unique Substring ($\mathsf{rSUS}$) problem, the range variant of the Shortest Unique Substring problem. We presented a $\mathcal{O}(nlogn)$-word data structure with $\mathcal{O}\left({log}_{w}n\right)$ query time, where $w=\Omega (logn)$ is the word size, for this problem. We also presented a $\mathcal{O}\left(n\right)$-word data structure with $\mathcal{O}\left(\sqrt{n}{log}^{ϵ}n\right)$ query time, where $ϵ>0$ is an arbitrarily small constant.

We leave the following related questions unanswered:

• Can we design an $\mathcal{O}\left(n\right)$-word data structure for the $\mathsf{rSUS}$ problem with polylogarithmic query time?
• Can we design an efficient solution for the k mismatches/edits variation of the $\mathsf{rSUS}$ problem, perhaps using the framework of [41]?
• Can our reduction from Section 2 be extended to other types of string regularities, such as shortest absent words [42]?