Faster Range LCP Queries in Linear Space

In this note we consider a variant of the longest common prefix (LCP) problem, called the range LCP problem. In this problem we store a text $T[1..n]$ in a data structure so that range LCP queries can be answered efficiently. A range LCP query $[\alpha ,\beta ]$ asks to return the length of the longest common prefix of any two suffixes with starting positions in a range $[\alpha ,\beta ]$,

where $\mathrm{𝖫𝖢𝖯}(i,j)$ denotes the length of the longest common prefix of $T[i..n]$ and $T[j..n]$.

This problem and its variants were considered in several papers, see e.g., [5, 9, 2, 3, 1, 10, 7]. The currently fastest data structure by Amir et al. [2] uses $O(n\log n)$ words of space and answers range LCP queries in $O(\log \log n)$ time. Henceforth we assume that a word of space consists of $\log n$ bits. The data structure with $O(n)$ space usage by Abedin et al. [1] supports queries in $O({\log }^{1+\epsilon }n)$ time for any constant $\epsilon >0$. The data structure of Matsuda et al. [10] uses $O(n{H}_0)$ bits of space where $H_0$ is the $0$-order entropy of the text $T$; however this space usage is achieved at a cost of significantly higher query time as their data structure supports queries in time $O(n^{\epsilon })$.

In this note we describe a new trade-off between the space usage and the query time: Our data structure uses linear space and supports queries in time $O({\log }^{\epsilon }n)$ for any constant $\epsilon >0$. Thus we achieve the same space usage as in [1] and query time that is close to [2]. Our solution combines the techniques from some previous papers with some new ideas. The compact data structure for predecessor queries by Grossi et al. [8] is also used in our construction.

We will say that a triple $(i,j,h)$ is a bridge if and $\mathrm{𝖫𝖢𝖯}(i,j)=h$. The total number of bridges is $O(n^2)$. However in order to answer a range LCP query it is sufficient to consider a subset of all bridges of size $O(n\log n)$ [2, 1]. Following the method of Abedin et al. [1], we consider special bridges that are defined below.

We consider the suffix tree of the text $T$ and divide its nodes into heavy and light nodes [11]. Let $\mathrm{size}(u)$ denote the number of leaves in the subtree rooted at $u$. The root is a light node. Exactly one child $u^{\prime }$ of every internal node $u$ is designated as a heavy node, specifically one with the largest $\mathrm{size}(u^{\prime })$ (ties are broken arbitrarily). All other nodes are light. Let ${\mathrm{\ell }}_i$ and ${\mathrm{\ell }}_j$ denote the leaves in the suffix tree that hold suffixes $T[i..n]$ and $T[j..n]$ respectively. Let $u$ denote the lowest common ancestor of ${\mathrm{\ell }}_i$ and ${\mathrm{\ell }}_j$ and let $u_i$ and $u_j$ denote the children of $u$ that are ancestors of ${\mathrm{\ell }}_i$ and ${\mathrm{\ell }}_j$ respectively. A bridge $(i,j,h)$ is a special bridge if one of the following conditions is satisfied:

1. 1.

   $u_i$ is a light node and $j=\min \{x\mid (i,x,h)\text{ is a bridge}\}$

2. 2.

   $u_j$ is a light node and $i=\max \{x\mid (x,j,h)\text{ is a bridge}\}$

In the rest of this paper a bridge will denote a special bridge.

Let $\mathrm{\Delta }=\log n$. For a bridge $(i,j,h)$ we will say that $i$ is its left leg, $j$ is its right leg, and $h$ is its height. We will say that a bridge $(i,j,h)$ is in the interval $[a,b]$ if $a\le i\le j\le b$. Let ${ℬ}_t$ denote the set of all bridges of height $t$.

By pigeonhole principle, there exists some value $\pi$, $1\le \pi \le \mathrm{\Delta }$, such that the total number of bridges in ${\cup }_{k\ge 0}{ℬ}_{\pi +k\mathrm{\Delta }}$ is bounded by $O(\frac{n\log n}{\mathrm{\Delta }})=O(n)$; see also [1, Section 5.1] We will say that all bridges in ${ℬ}_1\cup ({\cup }_{k\ge 0}{ℬ}_{\pi +k\mathrm{\Delta }})$ are base bridges. All other bridges are implicit bridges. Data structures for different categories of bridges are described below.

The total number of base bridges is $O(n)$. Furthermore we can find the maximum height base bridge in a query range by answering a variant of an orthogonal range searching query. Our data structure for base bridges is summarized in the following lemma.

Using Lemma 2, we can find the largest $h_0$ such that there is a base bridge of height $h_0$ in the query range $[\alpha ,\beta ]$. Now we explain how to find the largest $h$, , such that there is (an implicit) bridge of height $h$ in $[\alpha ,\beta -\mathrm{\Delta }]$.

The following properties of special bridges will be used.

Let $H_0$ denote the set of heights of base bridges. For every $h_0\in H_0$ we consider all bridges of height $h_0$ and construct the list of their left legs sorted in increasing order $L(h_0)=\{s_1,s_2,\mathrm{\dots },s_{n_0}\}$, where $n_0$ is the number of special bridges with height $h_0$. For each $k$, $1\le k\le \mathrm{\Delta }$, we also construct an array $R_{h_0,k}[1..n_0]$ so that $R_{h_0,k}[i]=\min \{j|\mathrm{𝖫𝖢𝖯}(s_i-k,j)\ge h_0+k\}$. Finally let

where $s_{i_a}$ is the successor of $(a+k)$ in $L(h_0)$ and $i_a$ is the position of $s_{i_a}$ in $L(h_0)$.

It remains to consider the case of bridges with right leg in the interval $[\beta -\mathrm{\Delta },\beta ]$ and of height $h$, . We apply the pigeonhole principle again. Let ${\mathrm{\Delta }}_1=\log \log n$. There exists some value ${\pi }_1$, $1\le {\pi }_1\le {\mathrm{\Delta }}_1$, such that the total number of bridges in ${\cup }_{k\ge 0}{ℬ}_{{\pi }_1+k{\mathrm{\Delta }}_1}$ is bounded by $O(\frac{n\log n}{{\mathrm{\Delta }}_1})=O(n\frac{\log n}{\log \log n})$. Let $H_1=\{{\pi }_1+k{\mathrm{\Delta }}_1\mid \mathrm{\hspace{0.17em}1}\le k\le (n-{\pi }_1)/{\mathrm{\Delta }}_1\}$. We will say that all bridges ${ℬ}_t$ where $t\in H_0\cup H_1$ are good bridges. All other bridges are bad bridges.

We will denote by ${\mathrm{Block}}_{t,h_0}$ the set of all bridges $(i,r,h)$ such that (a) $h\in H_0\cup H_1$ and for some $h_0\in H$ and (b) $t\mathrm{\Delta }+1\le r\le (t+1)\mathrm{\Delta }$ for some $k$, .

In order to answer a range LCP query $[\alpha ,\beta ]$ we need to identify the largest $h$ such that there is a bridge $(i,j,h)$ in $[\alpha ,\beta ]$. Our algorithm works in four stages:

1. 1.

   First, we find the largest $h_0$ such that there is a base bridge of height $h_0$ in $[\alpha ,\beta ]$. This step takes $O(\log \log n)$ time by Lemma 2.

2. 2.

   Then we find the largest $h_i$, where , such that there is an implicit bridge of height $h_i$ in $[\alpha ,\beta -\mathrm{\Delta }]$. This can be done in $O({\log }^{\epsilon }n\log \log n)$ time by Lemma 7

3. 3.

   We find the largest $h_n$ such that there is a good bridge of height $h_n>h_0$ with right leg in $[\beta -\mathrm{\Delta },\beta ]$. This step takes $O({\log }^{\epsilon }n)$ time by Lemma 10.

4. 4.

   Let $h_1=\max (h_0,h_i,h_n)$. We check if there is a bridge of height $h$ in $[\alpha ,\beta ]$ for each $h$, . By Lemma 5 we can check each candidate value of $h$ in $O({\log }^{\epsilon }n)$ time. Hence this step takes $O({\log }^{\epsilon }{\mathrm{\Delta }}_1)=O({\log }^{\epsilon }n\log \log n)$ time.

The total query time is $O({\log }^{\epsilon }n\log \log n)$. By replacing $\epsilon$ with a constant in the above construction, we obtain our final result.