Improved Circular Dictionary Matching

Consider a dictionary $𝒯=(T_1,T_2,\mathrm{\dots },T_d)$ of total length $n$ on an alphabet of size $\sigma$. In [36], Hon et al. show that, by storing a data structure of $n\log \sigma (1+o(1))+O(n)+O(d\log n)$ bits, it is possible to solve circular dictionary matching queries in $O((m+occ){\log }^{1+ϵ}n)$ time, where $m$ is the length of the pattern. This result holds under three assumptions: (i) the $T_h$’s are distinct and not periodic, (ii) no $T_h$ is a circular rotation of some other $T_{h^{\prime }}$, and (iii) the $T_h$’s have bounded aspect ratio, namely, $({\max }_{h=1}^d{T}_h)/({\min }_{h=1}^d{T}_h)=O(1)$. Assumption (ii) was made explicit only in the subsequent paper [32], where Hon et al. also mention that, in an extension of the paper, they will show how to remove assumptions (i-ii). Assumption (iii) is required to store a space-efficient data structure supporting longest common prefix (LCP) queries. In [33], Hon et al. sketched a new data structure for LCP queries that uses $O(n+d\log n)$ bits without requiring assumption (iii), but all details are again deferred to an extended version.

The main result of our paper is Theorem 1. In particular, we give two main contributions.

• $\mathrm{■}$

  We obtain results that are valid for an arbitrary dictionary $𝒯$, without imposing any restriction. To this end, in Section 3.2 we introduce a more general compressed suffix array for an arbitrary collection of strings. In particular, we support LCP functionality within only $O(n)+o(n\log \sigma )$ bits by using a sampling mechanism inspired by recent results [23, 17] on Wheeler automata.

• $\mathrm{■}$

  We provide a self-contained proof of our result and a full example of the data structure for solving circular dictionary matching queries. The original paper [36] contains the main ideas to extend Sadakane’s compressed suffix tree to a multiset of strings, but it is very dense and proofs are often only sketched or missing, which may explain why additional properties to potentially remove assumptions (i - iii) were only observed in subsequent papers. We will provide an intuitive explanation of several steps by using graphs (and in particular cycles, see Figure 2), consistently with a research line that has shown how the suffix array, the Burrows-Wheeler transform and the FM-index admit a natural interpretation in the graph setting [29, 3, 24, 22, 18, 4, 2, 25, 20].

We will also show that the time bound of Theorem 1 can be improved when the number of occurrences is large.

The paper is organized as follows. In Section 2 we introduce the circular dictionary matching problem. In Section 3 we define our compressed suffix tree. In Section 4 we present an algorithm for circular dictionary matching. Due to space constraints, most proofs and some auxiliary results can be found in the full version [21].

Let $T,P\in {\mathrm{\Sigma }}^{\ast }$ and $P$. For every $1\le i\le |P|-|T|+1$, we say that $T$ occurs in $P$ at position $i$ if $P[i,i+|T|-1]=T$.

Let $T\in {\mathrm{\Sigma }}^{\ast }$ and let $1\le i\le |T|$. The circular suffix $T_i$ of $T$ is the string $T[i,|T|]T[1,i-1]$. For example, if $T=cab$, then $T_1=cab$, $T_2=abc$ and $T_3=bca$.

Let $d\ge 1$, and let $T_1,T_2,\mathrm{\dots },T_d\in {\mathrm{\Sigma }}^{\ast }$ be nonempty strings. We say that $𝒯=(T_1,T_2,\mathrm{\dots },T_d)$ is a dictionary. We assume that the alphabet $\mathrm{\Sigma }$ is effective, that is, every character in $\mathrm{\Sigma }$ occurs in some $T_j$ (our results could be extended to larger alphabets by using standard tools such as dictionaries [42, 22]). Define the total length $n$ of $𝒯$ to be $n={\sum }_{k=1}^d|T_k|$. In the example of Figure 1(a), we have $d=3$ and $n=14$. For every $1\le k\le n$, the circular suffix ${𝒯}_k$ of $𝒯$ is the string $T_f(g)$, where $f$ is the largest integer in $\{1,2,\mathrm{\dots },d\}$ such that and $1\le g\le |T_f|$ is such that $k=({\sum }_{h=1}^{f-1}|T_h|)+g$. In other words, the circular suffix ${𝒯}_k$ is the circular suffix starting at position $k$ in the concatenation $T_1{T}_2\mathrm{\dots }{T}_d$. In Figure 1, if $k=13$, we have $f=3$, $g=2$ and ${𝒯}_{13}=abc$. Given a pattern $P\in {\mathrm{\Sigma }}^{\ast }$, where $|P|=m$, define:

and let $occ=|\mathrm{𝖢𝖽𝗆}(𝒯,P)|$. For example, if $P=abcbca$, in the example of Figure 1 we have $\mathrm{𝖢𝖽𝗆}(𝒯,P)=\{(1,9),(1,13),(2,10),(4,14)\}$ and $occ=4$.

The main result of this paper is the following.

We can also improve the time bound in Theorem 1 to $O(m\log n+\min \{occ\log n,n\log n+occ\})$, without needing to know the value $occ$ in advance. This is useful if $occ$ is large.

Following Hon et al. [36], we will build a data structure that extends Sadakane’s suffix tree to $𝒯$. We will achieve the space bound in Theorem 1 as follows. (i) We will store the FM-index of $𝒯$ using $n\log \sigma (1+o(1))+O(n)$ bits, see Theorem 9. (ii) We will introduce a notion of suffix array (Section 3.2) and a notion of longest comment prefix (LCP) array (Section 3.3). Storing the suffix array and LCP array explicitly would require $O(n\log n)$ bits so, in both cases, we will only store a sample (Theorem 10 and Theorem 13), leading to a compressed representation of both arrays. (iii) We will store some auxiliary data structures ($O(n)$ bits in total): 8 bitvectors (called $B_1$-$B_8$), a data structure supporting range minimum queries on the LCP array (see Section 3.3), a data structure storing the topology of the suffix tree (see Section 3.4), a data structure storing the topology of the auxiliary tree ${\mathrm{𝖲𝗎𝖿𝖿}}^{\ast }(𝒯)$ (see Section 4), and a data structure supporting range minimum queries on the auxiliary array $\mathrm{𝖫𝖾𝗇}$ (see Section 4).

Let us consider our dictionary $𝒯$ (recall that $n={\sum }_{k=1}^d|T_k|$). We can naturally define a bijective function $\varphi$ from the set $\{1,2,\mathrm{\dots },n\}$ to the set $\{(f,g)|\mathrm{\hspace{0.33em}1}\le f\le d,1\le g\le |T_f|\}$ such that, if $\varphi (k)=(f,g)$, then the $k$-th character of the concatenation $T_1{T}_2\mathrm{\dots }{T}_d$ is the $g$-th character of $T_f$. For example, in Figure 1 we have $\varphi (13)=(3,2)$. Let us define a bitvector $B_1$ to compute $\varphi$ and ${\varphi }^{-1}$ in $O(1)$ time. $B_1$ is the bitvector of length $n$ that contains exactly $d$ ones such that, for every $1\le h\le d$, the number of consecutive zeros after the $h$-th one is $|T_h|-1$ (see Figure 1(a)). Assume that $\varphi (k)=(f,g)$. Given $k$, we have $f={\mathrm{𝗋𝖺𝗇𝗄}}_1(B_1,k)$ and $g=k-{\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_1,f)+1$. Conversely, given $f$ and $g$, we have $k={\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_1,f)+g-1$. Note that in $O(1)$ time we can also compute $|T_h|$ for every $1\le h\le d$, because $|T_h|={\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_1,h+1)-{\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_1,h)$.

To exploit the circular nature of the dictionary, we will not sort the finite strings ${𝒯}_k$’s, but we will sort the infinite strings ${𝒯}_k^{\omega }$’s, and the suffix tree of $𝒯$ will be the trie of the ${𝒯}_k$’s. Notice that we may have ${𝒯}_k={𝒯}_{k^{\prime }}$ for distinct $1\le k,k^{\prime }\le n$ (in Figure 1, we have ${𝒯}_1={𝒯}_4={𝒯}_{13}={(abc)}^{\omega }$). The next lemma shows that this happens exactly when ${𝒯}_k$ and ${𝒯}_{k^{\prime }}$ have the same root.

The next step is to sort the “suffixes” ${𝒯}_k$’s. Since in general the ${𝒯}_k$’s are not pairwise distinct, we will use an ordered partition (see Figure 1(b)).

Note that ${𝒮}_j$ is well defined because it does not depend on the choice of $k\in D_j$ by the definition of $𝒟$. Note also that ${𝒮}_1\prec {𝒮}_2\prec \mathrm{\cdots }\prec {𝒮}_{n^{\prime }}$.

Let $1\le k\le n$, and assume that $\varphi (k)=(f,g)$. Define $\mathrm{𝗉𝗋𝖾𝖽}(k)$ as follows: (i) if $g\ge 2$, then $\mathrm{𝗉𝗋𝖾𝖽}(k)=k-1$, and (ii) if $g=1$, then $\mathrm{𝗉𝗋𝖾𝖽}(k)={\varphi }^{-1}(f,|T_f|)$. In other words, $\mathrm{𝗉𝗋𝖾𝖽}(k)$ equals $k-1$, modulo staying within the same string of $𝒯$. In Figure 1(a), we have $\mathrm{𝗉𝗋𝖾𝖽}(9)=8$, $\mathrm{𝗉𝗋𝖾𝖽}(8)=7$ but $\mathrm{𝗉𝗋𝖾𝖽}(7)=11$. For every $1\le k\le n$, we can compute $\mathrm{𝗉𝗋𝖾𝖽}(k)$ in $O(1)$ time by using the bitvector $B_1$: if $B_1[k]=0$, then $\mathrm{𝗉𝗋𝖾𝖽}(k)=k-1$, and if $B_1[k]=1$, then $\mathrm{𝗉𝗋𝖾𝖽}(k)={\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1({\mathrm{𝗋𝖺𝗇𝗄}}_1(B_1,k)+1)-1$.

If $U\subseteq \{1,2,\mathrm{\dots },n\}$, define $\mathrm{𝗉𝗋𝖾𝖽}(U)={\bigcup }_{k\in U}\mathrm{𝗉𝗋𝖾𝖽}(k)$. Since the function $\mathrm{𝗉𝗋𝖾𝖽}$ is a premutation of the set $\{1,2,\mathrm{\dots },n\}$, we always have $|\mathrm{𝗉𝗋𝖾𝖽}(U)|=|U|$ for every $U\subseteq \{1,2,\mathrm{\dots },n\}$. Let us prove that $\mathrm{𝗉𝗋𝖾𝖽}$ yields a permutation of the $D_j$’s.

For every $1\le j\le n^{\prime }$, let $\psi (j)=j^{\prime }$, where $\mathrm{𝗉𝗋𝖾𝖽}(D_j)=D_{j^{\prime }}$ as in Lemma 4. Notice that $\psi$ is permutation of $\{1,2,\mathrm{\dots },n^{\prime }\}$ because it is subjective: indeed, for every $1\le j^{\prime }\le n^{\prime }$, if we pick any $k^{\prime }\in D_{j^{\prime }}$, and consider $1\le k\le n^{\prime }$ such that $k^{\prime }=\mathrm{𝗉𝗋𝖾𝖽}(k)$ and $1\le j\le n^{\prime }$ such that $k\in D_j$, then $\mathrm{𝗉𝗋𝖾𝖽}(D_j)=D_{j^{\prime }}$. Moreover, for every $1\le j\le n^{\prime }$ define $\mu (j)={𝒮}_{\psi (j)}[1]$. By Lemma 4, we know that ${𝒮}_{\psi (j)}=\mu (j){𝒮}_j$ for every $1\le j\le n^{\prime }$.

We can visualize $\psi$ by drawing a (directed edge-labeled) graph $G_{𝒯}=(V,E)$, where $V=\{D_j|\mathrm{\hspace{0.33em}1}\le j\le n^{\prime }\}$ and $E=\{(D_{\psi (j)},D_j,\mu (j)|\mathrm{\hspace{0.33em}1}\le j\le n^{\prime }\}$, see Figure 2. Since $\psi$ is a permutation of $\{1,2,\mathrm{\dots },n^{\prime }\}$, then every node of $G$ has exactly one incoming edge and exactly one ongoing edge, so $G$ is the disjoint union of some cycles. Moreover, for every $1\le j\le n^{\prime }$ the infinite string that we can read starting from node $D_j$ and following the edges of the corresponding cycle is ${𝒮}_j$, because we know that ${𝒮}_{\psi (j)}=\mu (j){𝒮}_j$ for every $1\le j^{\prime }\le n^{\prime }$. For example, in Figure 2 the infinite string that we can read starting from $D_3$ is ${𝒮}_3={(bca)}^{\omega }$.

We will not explicitly build the graph $G_{𝒯}$ to solve circular dictionary matching queries, but $G_{𝒯}$ naturally captures the cyclic nature of $𝒯$ and will help us detect some properties of the $D_j$’s. For example, since we know that the infinite string starting from node $D_j$ is ${𝒮}_j$, and ${𝒮}_1\prec {𝒮}_2\prec \mathrm{\cdots }\prec {𝒮}_{n^{\prime }}$, we can easily infer the following properties (see Figure 2): if we consider two edges $(D_{j_1^{\prime }},D_{j_1},c)$ and $(D_{j_2^{\prime }},D_{j_2},d)$, then (i) if , then $c⪯d$, and (ii) if $c=d$ and , then . We can formalize these properties in our graph-free setting as follows.

We now want to extend the backward search [27] to our dictionary $𝒯$. We will again use $G_{𝒯}$ to guide our intuition. Given $U\subseteq \{1,2,\mathrm{\dots },n^{\prime }\}$ and given $c\in \mathrm{\Sigma }$, let $\mathrm{𝖻𝖺𝖼𝗄}(U,c)$ be the set of all $1\le j^{\prime }\le n^{\prime }$ such that there exists an edge $(D_{j^{\prime }},D_j,c)$ for some $j\in U$. For example, in Figure 2 we have $\mathrm{𝖻𝖺𝖼𝗄}(\{6,7,8\},b)=\{3,4,5\}$. Notice that $\{6,7,8\}$ is convex, and $\{3,4,5\}$ is also convex. This is true in general: $\mathrm{𝖻𝖺𝖼𝗄}(U,c)$ is always convex if $U$ is convex. Indeed, if and $j_1^{\prime },j_2^{\prime }\in \mathrm{𝖻𝖺𝖼𝗄}(U,c)$, then from the properties of $G_{𝒯}$ mentioned before Lemma 5 we first conclude that the edge leaving node $D_{j^{\prime }}$ is labeled with $c$, and then we infer that the node $D_j$ reached by this edge must be such that $j\in U$, which implies $j^{\prime }\in \mathrm{𝖻𝖺𝖼𝗄}(U,c)$. We can now formally define $\mathrm{𝖻𝖺𝖼𝗄}(U,c)$ in our graph-free setting and prove that $\mathrm{𝖻𝖺𝖼𝗄}(U,c)$ is convex if $U$ is convex.

Note that, if $U_1\subseteq U_2\subseteq \{1,2,\mathrm{\dots },n^{\prime }\}$ and $c\in \mathrm{\Sigma }$, then $\mathrm{𝖻𝖺𝖼𝗄}(U_1,c)\subseteq \mathrm{𝖻𝖺𝖼𝗄}(U_2,c)$.

Let us define the Burrows-Wheeler transform (BWT) of $𝒯$.

In other words, $\mathrm{𝖡𝖶𝖳}[j]$ is the label of the edge reaching node $D_j$ for every $1\le j\le n^{\prime }$ (see Figure 1(b) and Figure 2). The data structure that we will define in Theorem 9 is based on two sequences, ${\mathrm{𝖡𝖶𝖳}}^{\ast }$ and $B_2$, that are related to $\mathrm{𝖡𝖶𝖳}$ (see Figure 1(b)). The sequence ${\mathrm{𝖡𝖶𝖳}}^{\ast }$ is obtained from $\mathrm{𝖡𝖶𝖳}$ by sorting its elements. We know that for every pair of edges $(D_{j_1^{\prime }},D_{j_1},c)$ and $(D_{j_2^{\prime }},D_{j_2},d)$, if , then $c⪯d$, so ${\mathrm{𝖡𝖶𝖳}}^{\ast }[j]$ is the label of the edge leaving node $D_j$ for every $1\le j\le n^{\prime }$, which implies ${\mathrm{𝖡𝖶𝖳}}^{\ast }[j]={𝒮}_j[1]$ for every $1\le j\le n^{\prime }$. The bitvector $B_2$ has length $n^{\prime }$ and is obtained by marking with 1 the beginning of each equal-letter run in ${\mathrm{𝖡𝖶𝖳}}^{\ast }$. Formally, for every $1\le j\le n^{\prime }$, we have $B_2[j]=1$ if and only if $j=1$ or $(j>2)\wedge ({\mathrm{𝖡𝖶𝖳}}^{\ast }[j-1]\ne {\mathrm{𝖡𝖶𝖳}}^{\ast }[j])$. Since the alphabet is effective, the set $\{{\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_2,c),{\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_2,c)+1,{\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_2,c)+2,\mathrm{\dots },{\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_2,c+1)-2,{\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_2,c+1)-1\}$ consists of all $1\le j^{\prime }\le n^{\prime }$ such that the edge leaving node $D_{j^{\prime }}$ is labeled with $c$.

We can now extend the properties of the Burrows-Wheeler Transform and the FM-index to $𝒯$. In particular, we will show that $\mathrm{𝖡𝖶𝖳}$ if an encoding of $G_{𝒯}$. This result shows that $\mathrm{𝖡𝖶𝖳}$ is related to the eBWT of Mantaci et al. [40], but there are two main differences: (1) we do not need assumptions (i-ii) in Section 1 to define $\mathrm{𝖡𝖶𝖳}$ (in particular, the $T_h$’s need not be primitive), and (2) $\mathrm{𝖡𝖶𝖳}$ is an encoding of $G_{𝒯}$ but not of $𝒯$ (namely, $\mathrm{𝖡𝖶𝖳}$ encodes the cyclic nature of the $T_h$’s and not a specific circular suffix of each $T_h$). To extend the FM-index to $𝒯$, we will once again base our intuition on $G_{𝒯}$.

Recall that two (directed edge-labeled) graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic if there exists a bijection $f$ from $V_1$ to $V_2$ such that for every $u,v\in V_1$ and for every $c\in \mathrm{\Sigma }$ we have $(u,v,c)\in E_1$ if and only if $(f(u),f(v),c)\in E_2$. In other words, two graphs are isomorphic if they are the same graph up to renaming the nodes.

Note that, even if $\mathrm{𝖡𝖶𝖳}$ is an encoding of $G_{𝒯}$, it is not an encoding of $𝒯$ (in particular, from $G_{𝒯}$ we cannot recover $𝒯$). This is true even when all $D_j$’s are singletons because $G_{𝒯}$ only stores circular strings, so we cannot retrieve the bitvector $B_1$ the marks the beginning of each string (we cannot even retrieve the specific enumeration $T_1$, $T_2$, $\mathrm{\dots }$, $T_d$ of the strings in $𝒯$).

We know that $𝒟=(D_1,D_2,\mathrm{\dots },D_{n^{\prime }})$ is an ordered partition of $\{1,2,\mathrm{\dots },n\}$, and we know that ${𝒮}_1\prec {𝒮}_2\prec \mathrm{\cdots }\prec {𝒮}_{n^{\prime }}$. The suffix array of $𝒯$ should be defined in such a way that we can answer the following query: given $1\le j\le n^{\prime }$, return the set $D_j$.

In the following, we say that a position $1\le k\le n$ refers to the string $T_h$ if $h={\mathrm{𝗋𝖺𝗇𝗄}}_1(B_1,k)$. Every position refers to exactly one string. Notice that a set $D_j$ may contain elements that refer to the same string $T_h$. In Figure 1, we have $2,5\in D_3$, and both $2$ and $5$ refer to $T_1$. This happens because $T_1$ is not a primitive string. Let us show that, if we know any element of $D_j$ referring to $T_h$, we can retrieve all elements of $D_j$ referring to $T_h$.

For every $1\le h\le d$, let ${\rho }_h$ be the root of $T_h$. Then, $|T_h|$ is divisible by $|{\rho }_h|$, and for every $1\le k\le n$ the root $\rho ({𝒯}_k)$ of ${𝒯}_k$ is ${𝒯}_k[1,{\rho }_h]$, where $k$ refers to string $T_h$. For every $1\le h\le d$, let $k_h={\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_1,h)$ be the index in $\{1,2,\mathrm{\dots },n\}$ corresponding to the first character of $T_h$.

Fix $1\le j\le n^{\prime }$ and $1\le h\le d$, and let $k\in D_j$ any position referring to $T_h$. For every $k^{\prime }$ referring to $T_h$, we have $k^{\prime }\in D_j$ if and only if $\rho ({𝒯}_k)=\rho ({𝒯}_{k^{\prime }})$ (by Lemma 2), if and only if ${𝒯}_k[1,{\rho }_h]={𝒯}_{k^{\prime }}[1,{\rho }_h]$, if and only if $|k^{\prime }-k|$ is a multiple of $|{\rho }_h|$. Then, if $G$ is the set of all elements of $D_j$ referring to $T_h$, we have $G=\{k_h+(k-k_h+w|{\rho }_h|mod|T_h|)|\mathrm{\hspace{0.33em}0}\le w\le (|T_h|/|{\rho }_h|)-1\}$. For example, if Figure 1(b), if we consider $j=3$ and $h=1$ and we pick $k=5$, then $5\in D_3$, $5$ refers to $T_1$, ${\rho }_1=abc$, $|{\rho }_1|=3$, $|T_1|=6$, $k_1=1$ and $G=\{2,5\}$.

To compute $G$ we need to compute $|T_h|$ and $|{\rho }_h|$. We have already seen that we can compute $|T_h|$ in $O(1)$ time using $B_1$ (see Section 3.1), and we now store a bitvector $B_3$ to compute $|{\rho }_h|$ in $O(1)$ time (see Figure 3). The bitvector $B_3$ contains exactly $d$ ones, we have $B_3[1]=1$, and for every $1\le h\le d$ the number of consecutive zeros after the $h$-th one is $|{\rho }_h|-1$. Then, $|{\rho }_h|={\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_3,h+1)-{\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_3,h)$ for every $1\le h\le d$.

Let us define a suffix array for $𝒯$. Let $\sim$ be the equivalence relation on $\{1,2,\mathrm{\dots },n\}$ such that for every $1\le k,k^{\ast }\le n$ we have $k\sim k^{\ast }$ if and only if $k$ and $k^{\ast }$ belong to the same $D_j$ and refer to the same string $T_h$. Fix $1\le j\le n^{\prime }$. Notice that $D_j$ is the union of some $\sim$-equivalence classes. Let $D_j^{\prime }$ be the subset of $D_j$ obtained by picking the smallest element of each $\sim$-equivalence class contained in $D_j$. In Figure 1(b), for $j=3$, the partition of $D_3$ induced by $\sim$ is $\{\{2,5\},\{14\}\}$, so $D_3^{\prime }=\{2,14\}$. Then $\mathrm{𝖲𝖠}$ is the array obtained by concatenating the elements in $D_1^{\prime }$, the elements in $D_2^{\prime }$, $\mathrm{\dots }$, the elements in $D_{n^{\prime }}^{\prime }$ (see Figure 3), where the elements in $D_j^{\prime }$ are sorted from smallest to largest. Equivalently, the elements in each $D_j^{\prime }$ are sorted according to the indexes of the strings to which they refer (by definition, two distinct elements of $D_j^{\prime }$ cannot refer to the same string). We also define a bitvector $B_4$ to mark the beginning of each $D_j^{\prime }$ (see again Figure 3). More precisely, $B_4$ contains exactly $n^{\prime }$ ones and for every $1\le j\le n^{\prime }$ the number of consecutive zeros after the $j$-th one is $|D_j^{\prime }|-1$.

Fix $1\le k\le n$, where $k\in D_j$ refers to string $T_h$. Note that there exists $t$ such that $\mathrm{𝖲𝖠}[t]=k$ if and only if $k\in D_j^{\prime }$, if and only if $k_h\le k\le k_h+|{\rho }_h|-1$. Moreover, for every $k\in D_{j^{\prime }}$ we have that ${[k]}_{\sim }=\{k+w|{\rho }_h||\mathrm{\hspace{0.33em}0}\le w\le (|T_h|/|{\rho }_h|)-1\}$ is the set of all elements of $D_j$ referring to $T_h$. In particular, $\mathrm{𝖲𝖠}$ is an array of length $n^{\ast }={\sum }_{j=1}^{n^{\prime }}|D_j^{\prime }|={\sum }_{h=1}^d|{\rho }_h|$ (in Figure 3, we have $n^{\ast }=11$).

The suffix array $\mathrm{𝖲𝖠}$ has the desired property: given $1\le j\le n^{\prime }$, we can compute the set $D_j$ in $O(|D_j|)$ time as follows. We first retrieve $D_j^{\prime }$ by observing that its elements are stored in $\mathrm{𝖲𝖠}[t]$, $\mathrm{𝖲𝖠}[t+1]$, $\mathrm{𝖲𝖠}[t+2]$, $\mathrm{\dots }$, $\mathrm{𝖲𝖠}[t^{\prime }]$, where $t={\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_4,j)$ and $t^{\prime }={\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}}_1(B_4,j+1)-1$. Then, for every $k\in D_j^{\prime }$, we know that $k$ refers to string $T_h$, where $h={\mathrm{𝗋𝖺𝗇𝗄}}_1(B_1,k)$, and we can compute the set ${[k]}_{\sim }$ of all elements of $D_j$ referring to $T_h$ as shown above. Then, we have $D_j={\bigcup }_{k\in D_j^{\prime }}{[k]}_{\sim }$ and the union is disjoint.