Computing Smallest Suffixient Arrays
in Sublinear Time
June 30, 2026
Abstract
A suffixient array is a novel data structure that, when combined with an index providing direct access on a text \(T\), allows us to answer a variety of pattern matching queries. In this work, we show how to compute a smallest suffixient array for \(T[1\mathinner{.\,.}n]\) in \(O(\frac{n\log \sigma}{\sqrt{\log n}}+\min(r,\overline{r})\log^\epsilon n)\) time for any \(\epsilon > 0\), where \(\sigma\) is the alphabet size of \(T\) and \(r\) and \(\overline{r}\) are the numbers of equal-letter runs of the Burrows-Wheeler transforms of \(T\) and its reverse \(\overline{T}\), respectively. This time complexity becomes sublinear when \(\sigma\) is small enough and \(\min(r,\overline{r})=o(\frac{n}{\log^\epsilon n})\), yielding an asymptotic improvement over state-of-the-art algorithms. We also present a series of connected algorithmic results.
1 Introduction↩︎
One of the most relevant challenges in modern data compression is to represent in compressed space the huge and highly repetitive text collections that naturally arise in fields like Bioinformatics [1]–[3], so as to query them directly in compressed form. To do so, several measures of repetitiveness have been proposed to evaluate the compression effectiveness of those representations [4], [5]. Among others, suffixient arrays [6], [7] have received much attention in recent years. A suffixient array is a data structure that, once built on a text \(T[1\mathinner{.\,.}n]\), and provided with a representation of \(T\) that provides efficient random access to it, can efficiently find one occurrence of \(P\) in \(T\), and more generally, of each maximal substring of \(P\) that occurs in \(T\) (called “maximal exact matches”, or “MEMs”). This functionality is inferior to that of suffix arrays, but in exchange suffixient arrays can be much smaller on repetitive text collections, and they were shown to be faster in practice than than other well-known repetitiveness-aware compressed suffix arrays, such as the \(r\)-index [8].
More concretely, the size of a suffixient array is linear in the size of a suffixient set of \(T\), a subset of the positions of \(T\) such that any right-extension (i.e., one-character extension of a right-maximal substring) appears aligned at its rightmost position with some suffixient set position [6]. In a way, a suffixient set captures all the different substrings appearing in the text. It is natural then to aim for suffixient sets of minimum cardinality [9], which has been called \(\chi\) and studied as a repetitiveness measure in its own right [7], [10]–[12].
Besides the study of \(\chi\), a relevant challenge is how to efficiently find smallest suffixient sets and compute their suffixient arrays (which are the lexicographic order of the reversed prefixes that end at the positions of the suffixient sets). Cenzato et al.showed how to find smallest suffixient sets in linear time and compressed space [9], and how to test if a given set is suffixient [13]. Other constructions are linear-time online [11], or near-real-time [14]. The smallest suffixient arrays can also be constructed in linear time [7], [15].
In this paper we present the first sublinear-time algorithm to build smallest suffixient arrays under the RAM model of computation (where computer words of \(\Omega(\log n)\) bits are manipulated in constant time). We assume that the input text, which is over an alphabet \([0\mathinner{.\,.}\sigma)\), comes packed into \(O((n\log \sigma)/\log n)\) words, and build a smallest suffixient array in time \(O(n\log\sigma/\sqrt{\log n} + r\log^\epsilon n)\) for any \(\epsilon>0\), where \(r\) is the number of runs in the Burrows-Wheeler Transform (BWT) BW94? of \(T\). Measure \(r \le n\) is also sensitive to repetitiveness; in particular it holds that \(\chi \le 2r\) [10]. More precisely, our contributions are as follows:
We give a new linear-time algorithm for computing a smallest suffixient array starting from the BWT, the suffix array, and the longest common prefix array of \(T\). This offers an alternative to the algorithms of Cenzato et al. [7], which require those structures built on the reversed text instead. Our algorithm uses less working space than Fujimaru et al.’s [11] online algorithm for constructing suffixient sets. Further, it is very intuitive and easy to implement. As a first application, we use our algorithm to build suffixient arrays in compressed working space \(O((r+\overline{r})\log n)\), and time \(O(n(\log (r+\overline{r})+\log\log n))\), if the BWT of the reversed text has \(\overline{r}\) runs.
We optimize our algorithm to work in sublinear time under the packed setting, using recent data structures [16], [17] for sublinear time computation of the BWT, longest common extensions, and compressed suffix trees. We then compute a smallest suffixient array for \(T\) in \(O(n\log\sigma/\sqrt{\log n} + r\log^\epsilon n)\) time, which is sublinear when \(\log\sigma = o(\sqrt{\log n})\) and \(r = o(n/\log^\epsilon n)\) for some \(\epsilon>0\). The working space is \(O(n\log\sigma/\log n + r)\).
We show that, when \(\log\sigma=o(\sqrt{\log n})\), this result yields an \(o(n)\)-time algorithm to build a suffixient array whose size is an \(O(\log^{1+\epsilon} n)\)-approximation to \(\chi\). Further, size \(O(\chi)\) is not reached only when \(\chi = \Omega(n/\log^{\epsilon} n)\), that is, when the text is not so repetitive and thus it is not very interesting to have a suffixient array instead of a plain suffix array. By weaking the approximation factor to \(O(\log^{3/2+\epsilon}n)\), we reach the base construction time \(O(n\log\sigma/\sqrt{\log n})\).
We adapt Algorithm 6 of Cenzato et al. [7] to the packed setting, achieving the same sublinear time and working space on the reverse text.
Combining both results, we achieve \(O(n\log\sigma/\sqrt{\log n} + \min(r,\overline{r})\log^\epsilon n)\)-time computation of a smallest suffixient array for \(T\), within working space \(O(n\log\sigma/\log n + \min(r,\overline{r}))\). Since \(r = \Omega(\overline{r} \log n)\) on some string families [18], this symmetry yields strictly better complexity.
As a byproduct, we improve the \(O(n)\)-time construction of Shibata and Bannai [12] of an \(O(\chi(T))\)-sized string representation to \(O(n\log\sigma/\sqrt{\log n} + r\log^\epsilon n)\) time and \(O(n\log\sigma/\log n + r)\) space.
2 Terminology↩︎
We consider an alphabet \(\Sigma=[0, \sigma)\) of size \(\sigma\). A string \(x[1\mathinner{.\,.}n]\) of length \(n\) is a finite sequence \(x[1]x[2]\cdots x[n]\) of \(n\) elements in \(\Sigma\). The empty string \(\varepsilon\) is the unique string of length \(0\). We let \(\Sigma^*\) be the set of all strings over \(\Sigma\), \(\Sigma^+=\Sigma^*\setminus \{\varepsilon\}\), and \(\Sigma^k\) the set of strings of length \(k\) for \(k \ge 0\). We let \(x[i\mathinner{.\,.}j]=x[i]x[i+1]\cdots x[j]\) if \(1\le i\le j \le n\); if \(j < i\), we let \(x[i\mathinner{.\,.}j] = \varepsilon\), and use curved brackets to exclude the borders, e.g. \(x(i\mathinner{.\,.}j)=x[i+1]\cdots x[j-1]\). The concatenation of two strings \(x[1\mathinner{.\,.}n]\) and \(y[1\mathinner{.\,.}m]\) is the string \(x \cdot y = xy = x[1]\cdots x[n]y[1]\cdots y[m]\). A substring (or factor) of \(x\) is any string \(y\) such that \(x=vyz\) for some \(v, z\in \Sigma^*\). A prefix (resp. suffix) of \(x\) is any substring \(y\) such that \(x=yz\) (resp. \(x =zy\)) for some string \(z \in \Sigma^*\). We denote \(\mathcal{F}_x(k)\) the set of substrings of length \(k\) of \(x\) for any \(k\ge 0\), and \(\mathcal{F}_x\) the set of substrings of \(x\) of any possible length. The reverse of a string \(x[1\mathinner{.\,.}n]\), denoted as \(\overline{x}\), is the string \(x[n]x[n-1]\cdots x[1]\). The lexicographic order between two strings is defined as follows: \(x < y\) if \(y=xz\) with \(z\in\Sigma^+\), or \(x=zax'\) and \(y =zby'\) for some \(z, x',y'\in \Sigma^*\) and \(a,b\in \Sigma\) such that \(a < b\). The co-lexicographic order is defined as \(x <_{\mathtt{co}}y \iff \overline{x} < \overline{y}\).
We denote a string \(T[1\mathinner{.\,.}n]\) and call it a text to emphasize it is the target string to be compressed or indexed. Further, we assume \(T[n]=\mathtt{\$}\), where \(\mathtt{\$}\) is a special symbol that appears (only) at the end of \(T\) and is smaller than any other symbol in \(\Sigma\). We use lowercase letters like \(x,y,z\) to denote arbitrary strings.
The suffix array (SA) of \(T[1\mathinner{.\,.}n]\) is an array \(\mathtt{SA}[1\mathinner{.\,.}n]\) such that \(\mathtt{SA}[i]=j\) if \(T[j\mathinner{.\,.}n]\) is the \(i\)-th suffix of \(T\) in lexicographic order. By \(\mathtt{ISA}[1 \mathinner{.\,.}n]\) we denote the inverse permutation of the suffix array, that is, an array such that \(\mathtt{ISA}[i]=j \iff \mathtt{SA}[j]=i\) for \(i,j \in [1,n]\).
The longest common prefix of two strings \(x\) and \(y\), denoted \(\mathit{lcp}(x,y)\), is the longest string that is a prefix of \(x\) and \(y\). A longest common extension query \(\mathtt{LCE}(i, j)\) returns the length of the longest common prefix between the suffixes \(T[i\mathinner{.\,.}n]\) and \(T[j \mathinner{.\,.}n]\). The longest common prefix array is defined as \(\mathtt{LCP}[i]=\mathtt{LCE}(\mathtt{SA}[i],\mathtt{SA}[i-1])\) for \(i > 1\) and \(\mathtt{LCP}[1]=0\).
The Burrows–Wheeler transform (BWT) BW94? of a text \(T\) is a permutation obtained by sorting all the suffixes of \(T\) in lexicographic order and concatenating their preceding symbols. Formally, \(\mathtt{BWT}(T) = T[\mathtt{SA}[1]-1] \cdots T[\mathtt{SA}[n]-1]\) where we let \(T[0]=T[n]\). For any string \(x\), its run-length encoding is the unique sequence of pairs \((a_1,p_1),\ldots,(a_t,p_t)\) such that \(x=a_1^{p_1}\cdots a_t^{p_t}\) and \(a_{i-1}\neq a_{i}\) for all \(i \in [2,t]\). In particular, we use \(r\) to denote the size of the run-length encoding of \(\mathtt{BWT}(T)\), which is considered a measure of the repetitiveness of the text [4]. A position \(i\) in \(\mathtt{BWT}(T)\) is said to be a BWT run-break if \(\mathtt{BWT}[i-1]\neq \mathtt{BWT}[i]\).
We use \(\overline{\mathtt{BWT}},\overline{\mathtt{SA}},\overline{\mathtt{LCP}},\overline{\mathtt{ISA}},\overline{\mathtt{LCE}}\) and \(\overline{r}\), to denote the corresponding data structures and values for \(\overline{T}\) instead of \(T\).
2.1 Suffixient sets and supermaximal right extensions↩︎
The set of right extensions of \(T\) is \(E_T=\{xa\in\mathcal{F}_T\, |\,\exists b \neq a \text{ such that } xb \in \mathcal{F}_T\}\). A supermaximal right extension is a right extension that is not a proper suffix of any other right extension. The set of supermaximal right extensions of \(T\) is \(\mathtt{SRE}(T) =\{x\in E_T\,|\, \forall y \in E_T, y=zx \Rightarrow y=x\}\).
Definition 1. A suffixient set* \(\mathcal{X}\subseteq[1,n]\) for \(T[1\mathinner{.\,.}n]\) is a set of positions of \(T\) such that every supermaximal right extension \(x \in \mathtt{SRE}(T)\) appears as a suffix of some prefix \(T[1\mathinner{.\,.}i]\) with \(i \in \mathcal{X}\).*
Definition 2. The measure \(\chi(T)\) is the size of a smallest suffixient set for \(T\).
It is known that \(\chi(T)=|\mathtt{SRE}(T)|\) [7].
Definition 3. A suffixient array* \(A\) is a co-lexicographically sorted suffixient set. That is, if \(S\) is a suffixient set, then \(A[j]=i\) if and only if \(T[1\mathinner{.\,.}i]\) is the \(j\)-th prefix on the set \(\{T[1\mathinner{.\,.}i]\,|\, i\in S\}\) under \(<_{\mathtt{co}}\).*
Example 1. Let \(T = 010\underline{0}10\underline{1}0\underline{\mathtt{\$}}\), where the underlined positions correspond to a smallest suffixient set \(S=\{4,7,9\}\). The prefixes corresponding to those positions satisfy \(T[1\mathinner{.\,.}9] <_{\mathtt{co}}T[1\mathinner{.\,.}4] <_{\mathtt{co}}T[1 \mathinner{.\,.}7]\), hence a suffixient array is \(A = [9,4,7]\).
2.2 Computational model↩︎
We assume a computer word of size \(w=\Omega(\log n)\), where \(n = |T|\). The packed representation of a text \(T \in [0,\sigma)^n\) is a list obtained by storing \(\Theta(\log_\sigma n)\) letters per machine word, thus representing \(T\) in \(O(n/\log_{\sigma}n)=O(n \log \sigma/\log n)\) machine words. If \(T\) is given in the packed representation, we say that \(T\) is a packed string. We rely on the following results on packed strings, which yield sublinear times on small enough alphabets, that is, when \(\log\sigma = o(\sqrt{\log n})\).
Theorem 1 ([16]). LCE queries in a text \(T\in [0, \sigma)^n\) with \(\sigma=n^{O(1)}\) can be answered in \(O(1)\) time after \(O(n/\log_\sigma n)\)-time preprocessing of the packed representation of \(T\).
Theorem 2 ([16]). Given a packed text \(T\in [0, \sigma)^n\), the BWT of \(T\) can be constructed in \(O(n\log \sigma /\sqrt{\log n})\) time and \(O(n/\log_\sigma n)\) space.
Theorem 3 ([17]). Let \(\epsilon > 0\) be any constant. Given a packed text \(T\in [0, \sigma)^n\), we can construct a data structure in \(O(n\log \sigma / \sqrt{\log n})\) time and \(O(n/\log_\sigma n)\) working space, that can compute \(\mathtt{SA}[i]\) and \(\mathtt{ISA}[i]\) for any given index \(i\) in \(O(\log^\epsilon n)\) time.
3 Computing the suffixient array in linear time↩︎
In this section, we present a linear time algorithm that computes a smallest suffixient array starting from \(\mathtt{BWT}, \mathtt{SA}, \mathtt{LCP},\) and a longest common extension data structure \(\overline{\mathtt{LCE}}\) on the reversed text. Although this algorithm is unlikely to be faster than other state-of-the-art algorithms, it is conceptually very simple, and can be sped up by using proper sublinear-space data structures. In the following sections we show how to exploit this property in order to get an asymptotic improvement over state-of-the-art algorithms on most compressible texts.
We start by introducing a set of positions of \(T\) that is suffixient (though not minimal in general), characterized by the following lemma.
Lemma 1. Let \(xa\) be a supermaximal right extension of \(T\), for \(a \in \Sigma\). Then, there exists \(i\in[1,n]\) such that \(T[\mathtt{SA}[i]..\mathtt{SA}[i]+|x|]=xa\) and at least one of the following conditions is satisfied:
\(\mathtt{BWT}[i-1]\neq \mathtt{BWT}[i]\) and \(\mathtt{LCE}(\mathtt{SA}[i-1],\mathtt{SA}[i])=|x|\) or
\(\mathtt{BWT}[i+1]\neq \mathtt{BWT}[i]\) and \(\mathtt{LCE}(\mathtt{SA}[i+1],\mathtt{SA}[i])=|x|\).
Proof. As \(xa\) is a supermaximal extension of \(T\), there exists \(b \in \Sigma\) such that \(b \ne a\) and \(xa,xb \in \mathcal{F}_T\). Let us consider an integer interval \(U = \{i\,:\,T[\mathtt{SA}[i]..\mathtt{SA}[i]+|x|]=xa\}\) and let \(j\) be any index such that \(T[\mathtt{SA}[j]..\mathtt{SA}[j]+|x|]=xb\).
Assume first that \(j<k\) for all \(k \in U\). Then let \(i=\min U\). By the definition of \(U\), \(T[\mathtt{SA}[i]..\mathtt{SA}[i]+|x|]=xa\) holds. By the lexicographic order, we have \(\mathtt{LCE}(\mathtt{SA}[i-1],\mathtt{SA}[i]) \ge \mathtt{LCE}(\mathtt{SA}[j],\mathtt{SA}[i])=|x|\) and \(i-1 \not\in U\), so \(T[\mathtt{SA}[i-1]+|x|] = c \neq a\) and thus \(\mathtt{LCE}(\mathtt{SA}[i-1],\mathtt{SA}[i])=|x|\). Finally, we have \(\mathtt{BWT}[i-1]\neq \mathtt{BWT}[i]\) as otherwise \(xa\) would be a suffix of the string \(\mathtt{BWT}[i] xa \in \mathcal{F}_T\), which is a right extension because \(\mathtt{BWT}[i-1] x c = \mathtt{BWT}[i] x c \in \mathcal{F}_T\).
The case \(j>k\) for all \(k \in U\) is symmetric; we then have \(\mathtt{LCE}(\mathtt{SA}[i+1],\mathtt{SA}[i])=|x|\) and \(\mathtt{BWT}[i+1]\neq \mathtt{BWT}[i]\) for \(i = \max U\) (so \(T[\mathtt{SA}[i]..\mathtt{SA}[i]+|x|]=xa\)). 0◻ ◻
Definition 4. Let \(\mathcal{S}\) be the following set of substrings of \(T\): \[\mathcal{S}= \{T[\mathtt{SA}[i-1]\mathinner{.\,.}\mathtt{SA}[i-1]+\mathtt{LCP}[i]],T[\mathtt{SA}[i]\mathinner{.\,.}\mathtt{SA}[i]+\mathtt{LCP}[i]]\,:\, \mathtt{BWT}[i-1]\neq \mathtt{BWT}[i]\}.\]
See 1. Note that Lemma 1 implies the following observation.
The set \(\{\mathtt{SA}[i-1]+\mathtt{LCP}[i],\mathtt{SA}[i]+\mathtt{LCP}[i]\,:\, \mathtt{BWT}[i-1]\neq \mathtt{BWT}[i]\}\) is suffixient.
Lemma 2. A string \(u\) is a supermaximal right extension of \(T\) if and only if \(u \in \mathcal{S}\) and there is no string \(v \in \mathcal{S}\) such that \(u\) is a proper suffix of \(v\).
Proof. By the definition of \(\mathcal{S}\), each element of \(\mathcal{S}\) is a right extension of \(T\).
\((\Rightarrow)\) If \(u\) is a proper suffix of a right extension \(v \in \mathcal{S}\), then \(u\) is not supermaximal.
\((\Leftarrow)\) Assume \(u \in \mathcal{S}\) is not a proper suffix of any string \(v \in \mathcal{S}\). Then, by 1, it is not a proper suffix of any supermaximal right extension. Now assume that \(u\) is a proper suffix of a right extension \(v_1\) that is not supermaximal. Since \(v_1\) is not supermaximal, it is a proper suffix of a longer right extension \(v_2\), and so on. We continue this process until we reach a supermaximal string \(v\) that has all the previous ones—hence, \(u\)—as suffixes. 0◻ ◻
By 2, to obtain a suffixient set of the smallest cardinality, it suffices to remove the elements of \(\mathcal{S}\) that correspond to proper suffixes of another element of \(\mathcal{S}\). Checking this condition is equivalent to checking if an element is a proper prefix of another, when both are read backwards.
Let \(\overline{\mathcal{S}}\) be the set of reversals of substrings in \(\mathcal{S}\), which we treat as substrings of \(\overline{T}\). We say that a substring \(\overline{T}[n+1-j-\ell\mathinner{.\,.}n+1-j]\) is reverse supermaximal if \(T[j\mathinner{.\,.}j+\ell]\) is supermaximal in \(T\). By 1, every reverse supermaximal substring is contained in \(\overline{\mathcal{S}}\). Our goal is to filter out the remaining substrings from \(\overline{\mathcal{S}}\). The next corollary follows from 2.
Corollary 1. String \(X \in \overline{\mathcal{S}}\) is reverse supermaximal if and only if there is no other substring \(Y \in \overline{\mathcal{S}}\) that is prefixed by \(X\).
This leads to the problem given next. In the problem, we remove strings being proper prefixes of other strings and leave one string from many equal copies.
![Figure 1: Processing the BWT run-break at position i of the set \mathcal{S}. Substrings T[\mathtt{SA}[i]\mathinner{.\,.}\mathtt{SA}[i] +|x|] and T[\mathtt{SA}[i-1]\mathinner{.\,.}\mathtt{SA}[i-1] +|x|] are candidates to be supermaximal extensions of T. We add the pairs (n-(\mathtt{SA}[i]+|x|)+1, |x|+1) and (n-(\mathtt{SA}[i-1]+|x|)+1, |x|+1) to the multiset \overline{\mathcal{S}}, which represents the starting positions and length of the occurrences of those reversed candidates in \overline{T}.](/article/2607.00204/_pdflatex/mhycjgzv.png "fig:")
3.0.0.1 Deleting prefixes among a set of substrings.
We define the following auxiliary problem. Among equal substrings, we retain an arbitrary one.
Example 2. If the substrings are \(\mathtt{010},\mathtt{01},\mathtt{1010},\mathtt{010},\mathtt{1},\mathtt{101}\), the output should contain substrings \(\mathtt{010},\mathtt{1010}\). In the problem, substrings are represented in \(O(1)\) space as position pairs.
This problem can be solved using weighted ancestor queries on the suffix tree [19]. Below we show an arguably simpler algorithm. More importantly, in the next section we show how to make it work in sublinear time (for sufficiently small \(t\)). Notably, our algorithm does not require to sort the substrings lexicographically; it suffices to sort the corresponding suffixes of \(T\).
We say that index \(i\) is a (proper) prefix of (or is equivalent to) index \(j\) if \(T[s_i \mathinner{.\,.}e_i)\) is a (proper) prefix of \(T[s_j \mathinner{.\,.}e_j)\) (or \(T[s_i \mathinner{.\,.}e_i)=T[s_j \mathinner{.\,.}e_j)\), resp.).
In the solution to the problem, we store a decremental doubly-linked list of the indices in \([1,t]\). We consider the substrings in the order of non-decreasing lengths. When an index is considered, we only check if it is a prefix of any of its neighbours in the list and then remove it from the list. Technically, the list is represented as \(\mathit{next}/\mathit{prev}\) pointers; see 2.
Lemma 3. \(m\) integers in \([0, n]\) can be sorted in \(O(\sqrt{n}+m)\) time.
Proof. We treat an integer \(x \in [0, n)\) as a pair \((\lfloor x/\lfloor \sqrt{n} \rfloor \rfloor,x \bmod \lfloor \sqrt{n} \rfloor)\). We sort the resulting \(m\) pairs using Radix Sort in \(O(\sqrt{n}+m)\) time [20]. 0◻ ◻
Lemma 4. 2 solves the Deleting Prefixes problem in \(O(\min(t+\sqrt{n},t \log t)+tq)\) time provided that any \(\mathtt{LCE}\) and \(\mathtt{ISA}\) query on \(T\) is answered in \(O(q)\) time.
Proof. Correctness: First we show that \(\mathit{good}[i]=\mathbf{false}\) at the conclusion of the algorithm if and only if for some \(j \in [1,t] \setminus \{i\}\), (1) \(i\) is a proper prefix of \(j\) or (2) \(j\) is equivalent to \(i\) and \(j>i\).
\((\Rightarrow)\) If \(\mathit{good}[i]=\mathbf{false}\), let \(j\) be the neighbour of \(i\) in the current list that caused this assignment. Naturally, we have \(j \in [1,t] \setminus \{i\}\). If \(i\) is a proper prefix of \(j\), condition (1) is satisfied. If \(i\) is equivalent to \(j\), we have \(e_i-s_i=e_j-s_j\), so \(j>i\) by the order in which the list is processed. Hence, condition (2) is satisfied.
\((\Leftarrow)\) Assume that \(i,j \in [1,t]\), with \(i \ne j\), satisfy (1) \(i\) is a proper prefix of \(j\) or (2) \(j\) is equivalent to \(i\) and \(j>i\). In either case, when index \(i\) is considered in the foreach-loop, index \(j\) is still present in the list. In case (1), we assume that \(j>i\), as the opposite case is symmetric. Let \(i_1=i,i_2,\ldots,i_{w-1},i_w=j\) be all indices in between those two in the list at this moment of the algorithm. Each of the substrings \(T[s_{i_l} \mathinner{.\,.}e_{i_l})\) for \(l \in [1,w]\) has length at least \(e_i-s_i\), so each of them has \(T[s_i \mathinner{.\,.}e_i)\) as a prefix, as otherwise \(T[s_1 \mathinner{.\,.}n] \le \cdots \le T[s_t \mathinner{.\,.}n]\) would not be satisfied. Hence, \(\mathit{good}[i]=\mathbf{false}\) because of \(i_2=\mathit{next}[i]\).
Now we show that substrings are reported in lexicographic order. Assume that consecutive indices \(i,i'\) such that \(i<i'\) are present in the output of the algorithm. As both indices are in the output, none of the strings \(u:=T[s_i \mathinner{.\,.}e_i]\), \(v:=T[s_{i'} \mathinner{.\,.}e_{i'}]\) is a prefix of the other (in particular, \(u \ne v\)). Hence, there is a position \(q \in [1,\min(|u|,|v|)]\) such that \(u[1 \mathinner{.\,.}q) = v[1 \mathinner{.\,.}q)\) and \(u[q] \ne v[q]\). We have \(T[s_i \mathinner{.\,.}n] \le T[s_{i'} \mathinner{.\,.}n]\), so \(u[q] < v[q]\), i.e., \(u<v\).
Complexity: Sorting suffixes \(T[s_i \mathinner{.\,.}n]\) by the values \(\mathtt{ISA}[s_i]\) as well as values \(e_i-s_i\) takes \(O(\sqrt{n}+t)\) time by 3 or \(O(t \log t)\) time using merge sort. In addition, the algorithm performs \(O(t)\) operations and \(O(t)\) \(\mathtt{LCP}\) (and \(\mathtt{ISA}\)) queries. Indeed, an \(\mathit{lcp}\) query on substrings of \(T\) can be answered using an \(\mathtt{LCE}\) query on the corresponding prefixes of \(T\) and a comparison with the substrings’ lengths. 0◻ ◻
3.0.0.2 Wrap-up.
Let us analyze the time complexity of the algorithm. We compute the \(\mathtt{BWT}\), \(\mathtt{SA}\) and \(\mathtt{ISA}\) for \(T\) and \(\overline{\mathtt{ISA}}\) for \(\overline{T}\) in \(O(n)\) time [21]. We compute in \(O(n)\) time data structures for answering \(\mathtt{LCE}\) queries on \(T\) and \(\overline{\mathtt{LCE}}\) queries on \(\overline{T}\) in \(O(1)\) time [22]. This allows us to compute the set \(\mathcal{S}\), and hence the set \(\overline{\mathcal{S}}\), in \(O(n)\) time. We then use 2 on \(\overline{T}\) to identify reverse supermaximal substrings in \(\overline{\mathcal{S}}\). By 4, the algorithm works in \(O(n)\) time.
By definition, if \(\overline{T}[n+1-(j+\ell)\mathinner{.\,.}n+1-j)\) is such a substring, then \(T[j \mathinner{.\,.}j+\ell)\) is a supermaximal right extension of \(T\). By taking all indices \(j+\ell-1\) over all such pairs, we obtain a suffixient set of the smallest cardinality.
In the output to the Deleting Prefixes problem, the substrings (of \(\overline{T}\)) are sorted according to lexicographic order, so they represent a co-lexicographic order of the original substrings of \(T\). We leave one copy from each set of equal substrings to ensure that the size of the suffixient array is smallest. Thus we have computed a smallest suffixient array of \(T\) in the desired time and space complexity, recall Def. 3.
3.0.0.3 Building in compressed space.
As a first application of our algorithm, consider the particularly interesting scenario of building the suffixient array within repetitive-aware space. Prezza [23] showed how to build the run-length-encoded \(\mathtt{BWT}\) within \(O(r)\) space in time \(O(n\log r)\), providing access to the \(\mathtt{BWT}\) in time \(O(\log\log(n/r))\). Gagie et al. [8] extend this construction to add structures that compute \(\mathtt{SA}\), \(\mathtt{ISA}\), and \(\mathtt{LCP}\) in time \(O(\log(n/r))\). Their construction uses \(O(r\log(n/r))\) space and \(O(n(\log r + \log\log (n/r)))\) time.
To apply our algorithm, we build those structures for both \(T\) and \(\overline{T}\). We then compute \(\mathcal{S}\) and \(\overline{\mathcal{S}}\) in time \(O(r\log(n/r))\), whereas the prefix deletion phase takes \(O(r \log r + r\log(n/\overline{r}))\) time. The total time is then \(O(r\log n) \subseteq O(n\log r)\) and the extra working space is \(O(r)\). (We improve this result later, in Corollary 4.)
Theorem 4. A suffixient array of a string \(T \in [0, \sigma)^n\), where the \(\mathtt{BWT}\) of \(T\) has \(r\) runs and that of \(\overline{T}\) has \(\overline{r}\) runs, can be computed in \(O(n(\log r^*+\log\log(n/r^*)))\) time using \(O(r^*\log (n/r^*))\) working space, where \(r^* = \max(r,\overline{r})\).
4 An \(O(p(n,\sigma) {+} r\log^\epsilon n)\) time algorithm for computing \(\chi\)↩︎
Let \(p(n,\sigma) = \frac{n\log \sigma}{\sqrt{\log n}}\) and \(p'(n,\sigma) = \frac{n \log \sigma}{\log n}\). In this section, we present an algorithm that, given a packed string \(T\), computes a smallest suffixient array in \(O(p(n,\sigma) + r\log^\epsilon n)\) time for any desired constant \(\epsilon > 0\), and uses \(O(p'(n,\sigma)+r)\) working space. We use the algorithm from the previous section but replace the specific data structures with their sublinear-time counterparts.
Theorem 5. A smallest suffixient array of a packed string \(T \in [0, \sigma)^n\) can be computed in \(O(p(n,\sigma) + r\log^\epsilon n)\) time for any desired constant \(\epsilon > 0\), using \(O(p'(n,\sigma)+r)\) working space. As a by-product, the algorithm computes \(\mathtt{SRE}(T)\).
Proof. We compute the (packed) \(\mathtt{BWT}\) of \(T\) in \(O(p(n,\sigma))\) time and \(O(p'(n,\sigma))\) space [16]. Since the \(\mathtt{BWT}\) is packed in \(O(p'(n,\sigma))\) space, we can identify all run breaks, in each machine word separately, in \(O(p'(n,\sigma)+r)\) time: We precompute in time \(O(\sqrt{n}\log n)\) a table that, for every sequence of packed symbols fitting in \(\lfloor \frac{1}{2}\log n\rfloor\) bits, records the run breaks inside the sequence.
We compute the packed representation of \(\overline{T}\). To this end, we reverse the list of words representing \(T\) and also need to reverse the symbols within each word. To this end, we precompute in time \(O(\sqrt{n} \log n)\) a table that stores the reverse of every sequence of packed symbols fitting in \(\lfloor \frac{1}{2} \log n \rfloor\) bits. Now after \(O(p(n,\sigma))\) time and \(O(p'(n,\sigma))\) space preprocessing, we can compute \(\mathtt{SA}[i]\) and \(\overline{\mathtt{ISA}}[i]\) for any \(i\) in \(O(\log^\epsilon n)\) time [17], and after \(O(p'(n,\sigma))\) time preprocessing, the \(\mathtt{LCE}\) of any two positions in \(T\) and in \(\overline{T}\) can be computed in \(O(1)\) time [16].
With these data structures, the set \(\mathcal{S}\), and hence the set \(\overline{\mathcal{S}}\), can be computed in \(O(p(n,\sigma)+r\log^\epsilon n)\) time and \(O(p'(n,\sigma)+r)\) space (via \(2r\) \(\mathtt{SA}\), \(\overline{\mathtt{ISA}}\), and \(\mathtt{LCE}\) queries on the \(\mathtt{BWT}\) run limits). This allows creating the lists so that 2 runs in \(O(r+\sqrt{n})\) time, by 4. See 3. 0◻ ◻
4.0.0.1 An always-sublinear-time approximation.
When \(\log\sigma=o(\sqrt{\log n})\), Theorem 5 yields \(o(n)\) construction time if there is constant \(\epsilon>0\) such that \(r = o(n/\log^\epsilon n)\). We can ensure \(o(n)\) time for any \(r\) by building an approximation, for any fixed \(\epsilon\): We first build \(\mathtt{BWT}\) in \(o(n)\) time, which yields \(r\). If \(r \le n/\log^{\epsilon/2} n\), we can just apply Theorem 5. Otherwise, we return instead the suffixient set defined by the endpoints of \(\mathcal{S}\) (Def. 4), which is of size \(2r\) and available from \(\mathtt{BWT}\), \(\mathtt{SA}\), and \(\mathtt{LCP}\), all of which are built in \(o(n)\) time. This size is an \(O(\log^{1+\epsilon} n)\)-approximation to the optimal \(\chi\), because \(2r = O(n)\) and \(\chi \ge \delta = \Omega(r /(\log \delta \log(n/\delta)))\) [24], where \(\delta\) is the normalized substring complexity [25]. When \(r = \Omega(n/\log^{\epsilon/2} n)\), since \(\delta = \Omega(r/\log^2 n)\) [24], it holds \(n/\delta = O((n/r)\log^2 n) = O(\textrm{polylog}\,n)\). Thus \(\chi = \Omega(r/(\log\delta\log(\textrm{polylog}\,n))) = \Omega(n/(\log^{\epsilon/2} n \log n \log\log n)) = \Omega(n/\log^{1+\epsilon} n)\).
Further, if we switch to just returning the endpoints of Def. 4 when we detect that \(r > (n\log\sigma/\sqrt{\log n})/\log^{\epsilon/2} n\), then we ensure total time \(O(p(n,\sigma))\), at the price of worsening the approximation to \(O(\log^{3/2+\epsilon} n)\).
Corollary 2. A suffixient array of a string \(T \in [0, \sigma)^n\), of size \(O(\chi \log^{1+\epsilon} n)\) for any desired constant \(\epsilon>0\), can be computed in \(o(n)\) time using \(O(p'(n,\sigma))\) working space plus the output size. The suffixient array is of size \(O(\chi)\) whenever \(r = O(n/\log^\epsilon n)\). Further, we can compute in \(O(p(n,\sigma))\) time a suffixient array of size \(O(\chi \log^{3/2+\epsilon} n)\), which is of size \(\chi\) when \(r = O(n\log\sigma/\log^{1/2+\epsilon} n)\).
4.0.0.2 Replacing the \(r\) factor by \(\min(r,\overline{r})\).
Cenzato et al. [7] shows how to construct a smallest suffixient array for \(T\) in linear time, starting from the arrays \(\overline{\mathtt{BWT}}\), \(\overline{\mathtt{SA}}\), and \(\overline{\mathtt{LCP}}\), of the reversed text. We adapt their algorithm using the data structures of Kempa and Kociumaka [16], obtaining the following result (see Appendix 7).
Theorem 6. A smallest suffixient array of a string \(T \in [0, \sigma)^n\) can be computed in \(O(p(n,\sigma) + \overline{r}\log^\epsilon n)\) time for any constant \(\epsilon > 0\), using \(O(p'(n,\sigma)+\overline{r})\) working space.
By combining 5 and 6, and because \(r\) and \(\overline{r}\) can be computed in \(O(p(n,\sigma))\) time, we obtain the following.
Corollary 3. A smallest suffixient array of a string \(T \in [0, \sigma)^n\) can be computed in \(O(p(n,\sigma) + \min(r,\overline{r})\log^\epsilon n)\) time for any desired constant \(\epsilon > 0\), using \(O(p'(n,\sigma)+\min(r,\overline{r}))\) working space.
Finally, repeating the same steps of Theorem 4 over this algorithm, which uses only the structures on \(\overline{T}\), we have the following improved result.
Corollary 4. A suffixient array of a string \(T \in [0, \sigma)^n\), where the \(\mathtt{BWT}\) of \(\overline{T}\) has \(\overline{r}\) runs, can be computed in \(O(n(\log \overline{r}+\log\log(n/\overline{r})))\) time using \(O(\overline{r}\log (n/\overline{r}))\) working space.
5 Computing \(O(\chi(T))\)-Sized String Representation↩︎
Shibata and Bannai [12] showed recently that a string \(T\) can be represented in \(O(\chi(T))\) space. They presented (in Thm. 15) an \(O(n)\)-time algorithm computing this representation (if \(T\) is over a linear-time-sortable alphabet). We show that an \(O(\chi(T))\)-sized representation of \(T\) can be computed in sublinear time (for small enough \(\sigma\) and \(r\)).
The next lemma follows from efficient construction of wavelet trees [26].
Lemma 5. For a packed text \(T \in \Sigma^n\), we can compute for each letter \(c \in \Sigma\) a position \(i\) such that \(T[i]=c\) or state that no such position exists in \(O(p(n,\sigma)+\sigma \log \sigma)\) time and \(O(p'(n,\sigma)+\sigma)\) space.
Proof. A \(\mathit{select}_a(i)\) query for \(T\) consists in computing the \(i\)th leftmost occurrence of character \(a \in \Sigma\) in \(T\) (or stating that such an occurrence does not exist). A wavelet tree for \(T\) allows to answer \(\mathit{select}_a\) queries in \(O(\log \sigma)\) time [27], [28]. Thus queries \(\mathit{select}_a(1)\) for all \(a \in \Sigma\) can be answered in \(O(\sigma \log \sigma)\) time with the data structure. Finally, a wavelet tree can be constructed in \(O(p(n,\sigma))\) time [26] and occupies \(O(p'(n,\sigma))\) space. 0◻ ◻
The representation of Shibata and Bannai is a substring equation system.
Definition 5 ([12]). An instance of a substring equation system* (SES in short) for a string \(T\in\Sigma^n\) is a triple \((n,\mathsf{Eq},\mathsf{Ch})\). Each element of \(\mathsf{Eq}\) is a triple \((i,j,\ell)\) with \(i,j \in [1,n]\) and \(1\le \ell \le n-\max(i,j)+1\), representing the equation \(T[i\mathinner{.\,.}i+\ell)=T[j\mathinner{.\,.}j+\ell)\). Each element of \(\mathsf{Ch}\) is a pair \((k,c)\) with \(k \in [1,n]\) and \(c\in\Sigma\), representing the equation \(T[k]=c\). We say that \((n,\mathsf{Eq},\mathsf{Ch})\) represents \(T\) if \(T\) is the unique string in \(\Sigma^n\) satisfying all constraints in \(\mathsf{Eq}\) and \(\mathsf{Ch}\). The size of the system is defined as \(|\mathsf{Eq}|+|\mathsf{Ch}|\).*
We now recall how the SES for \(T\) of size \(O(\chi(T))\) is constructed [12]. The set \(\mathsf{Ch}\) is obtained by taking one arbitrary occurrence in \(T\) of each distinct character. The set \(\mathsf{Eq}\) includes the following equations: for every two \(yxa,y'xa' \in \mathtt{SRE}(T)\), where \(x\) is the longest common suffix of \(yx\) and \(y'x\), pick arbitrary occurrences \(T[s \mathinner{.\,.}e)=yxa\) and \(T[s' \mathinner{.\,.}e')=y'xa'\) and create an equation \(T[s+|y| \mathinner{.\,.}s+|yx|)=T[s'+|y'| \mathinner{.\,.}s'+|y'x'|)\). Shibata and Bannai show how all these equations can be expressed by just \(\chi(T)-1\) equations using a construction based on a compacted trie of substrings of \(T\).
Theorem 7. For a text \(T \in [0, \sigma)^n\) such that \(\log \sigma \le \sqrt{\log n}\), an SES of size \(O(\chi(T))\) representing \(T\) can be computed in \(O(p(n,\sigma)+r\log^\epsilon n)\) time and \(O(p'(n,\sigma)+r)\) space.
Proof. Since \(\sigma \le 2^{\sqrt{\log n}}\), the set \(\mathsf{Ch}\) can be computed via 5 in \(O(p(n,\sigma))\) time and \(O(p'(n,\sigma))\) space. For \(\mathsf{Eq}\), we present a construction that avoids building the compacted trie (and explicitly sorting the trimmed reversals of supermaximal right extensions).
We compute \(\mathtt{SRE}(T)\) using 5. For each \(T[i \mathinner{.\,.}j] \in \mathtt{SRE}(T)\), we construct a substring \(\overline{T}[n+2-j \mathinner{.\,.}n+1-i] = \overline{(T[i \mathinner{.\,.}j))}\) (note that the last symbol of the supermaximal right extension is removed). Let \(\overline{T}[s_1 \mathinner{.\,.}e_1),\ldots,\overline{T}[s_t \mathinner{.\,.}e_t)\) be the resulting substrings, where \(t=\chi(T)\). Then the set \(\mathsf{Eq}\) is constructed using [alg:Eq] (which resembles 2).
Reorder substrings \(\overline{T}[s_i \mathinner{.\,.}e_i)\) so that \(\overline{T}[s_1 \mathinner{.\,.}n] \le \cdots \le \overline{T}[s_t \mathinner{.\,.}n]\) \(\mathsf{Eq} \gets \emptyset\)
[alg:Eq] works in \(O(t+\sqrt{n})\) time—we use 3 for sorting—after a preprocessing that computes \(\overline{\mathtt{ISA}}\) [17] and the data structure for answering \(\overline{\mathtt{LCE}}\) queries [16]. The preprocessing itself takes \(O(p(n,\sigma))\) time and \(O(p'(n,\sigma))\) space. The returned set satisfies \(|\mathsf{Eq}|=\chi(T)-1\). We just need to argue that it expresses all the desired equations. The triple inserted to \(\mathsf{Eq}\) corresponds to equation \[T[n+1-(s_i+\ell-1) \mathinner{.\,.}n+1-s_i]=T[n+1-(s_{i+1}+\ell-1) \mathinner{.\,.}n+1-s_{i+1}],\] i.e., \(\overline{T}[s_i \mathinner{.\,.}s_i+\ell)=\overline{T}[s_{i+1} \mathinner{.\,.}s_{i+1}+\ell)\) where \(\ell=\mathit{lcp}(\overline{T}[s_i \mathinner{.\,.}n],\overline{T}[s_{i+1} \mathinner{.\,.}n])\). Thus every triple inserted into \(\mathsf{Eq}\) implies an equation that holds in \(\overline{T}\) (hence, in \(T\)). Let us consider indices \(j,k\) such that \(1 \le j < k \le t\) and denote \(d=\mathit{lcp}(\overline{T}[s_j \mathinner{.\,.}e_j),\overline{T}[s_k \mathinner{.\,.}e_k))\). We need to argue that the equation \[(*)\,\, \overline{T}[s_j \mathinner{.\,.}s_j+d)=\overline{T}[s_k \mathinner{.\,.}s_k+d)\] is implied by the equations in \(\mathsf{Eq}\). Because the suffixes \(\overline{T}[s_1\mathinner{.\,.}n],\ldots,\overline{T}[s_t \mathinner{.\,.}n]\) are ordered lexicographically, \(\overline{T}[s_i \mathinner{.\,.}s_i+d)=\overline{T}[s_j \mathinner{.\,.}s_j+d)\) holds for all \(i \in [j,k]\). This implies that \(\overline{\mathtt{LCE}}(i,i+1) \ge d\) for all \(i \in [j,k-1]\), and equation \((*)\) is implied by the equations created for \(i \in [j,k-1]\). 0◻ ◻
6 Future Work↩︎
We have shown how to compute a suffixient array for \(T[1\mathinner{.\,.}n]\) in \(O(n\log \sigma/\sqrt{\log n}\) \(+\min(r,\overline{r})\log^\epsilon n)\) time for any \(\epsilon > 0\).
While further reducing the first term hits conditional lower bounds as long as we build on top of the BWT [16], the second term comes from computing \(2\min(r,\overline{r})\) direct and inverse suffix array queries using structures that can be built in sublinear time [16]. It could be possible to run those queries faster, for example in batch rather than one by one.
We also plan to work further on the line of Theorem 4, by considering conversions from/to other compressed formats (see, e.g., [29]). It might be possible, for example, to find connections with other compressed indexes that build on right-maximal strings, like CDAWGs [30].
7 Sublinear time adaptation of Cenzato et al.’s algorithm↩︎
Cenzato et al. [7] show how to construct a smallest suffixient array for \(T\) in linear time, starting from the array \(\overline{\mathtt{BWT}}\), the suffix array \(\overline{\mathtt{SA}}\), and the LCP array \(\overline{\mathtt{LCP}}\) of the reversed text. Additionally, it uses an array \(R\) to keep information about the last position that is candidate to be a super-maximal extension for each \(c \in \Sigma\). More precisely, in \(R[c].len\) is stored the \(\overline{\mathtt{LCP}}\) value for the last candidate \(c\)-run break, in \(R[c].pos\) is stored its position in \(T\), and \(R[c].active\) is a flag telling if \(R[c].pos\) was already added to the suffixient set (which case it is set to false) or not.
The algorithm sequentially scans \(\overline{\mathtt{BWT}}\). For a run \(\overline{\mathtt{BWT}}[i - 1 - j \mathinner{.\,.}i - 1] = c^{j + 1}\), it iterates from \(k = i - j\) to \(i - 1\) and keeps the minimum value within \(\overline{\mathtt{LCP}}[i - 1 - j \mathinner{.\,.}k]\) in a variable \(m\) and it updates \(\overline{\mathtt{LF}}[c] = \overline{\mathtt{LF}}[c] + 1\). For a run-break \(\overline{\mathtt{BWT}}[i - 1, i] = ac\), it keeps the minimum value within \(\overline{\mathtt{LCP}}[i]\) and \(m\) and stores it in \(m\), updates \(\overline{\mathtt{LF}}[c] = \overline{\mathtt{LF}}[c] + 1\) and calls to \(eval\) to evaluate if \(m < R[a].len\) (such a case \(R[a].pos\) is added to the suffixient set computed so far, \(m\) is stored in \(R[a].len\) and \(R[a].active\) is set to \(false\)), and it calls to \(eval\) to determine if \(\overline{\mathtt{LCP}}[\overline{\mathtt{LF}}[\overline{\mathtt{BWT}}[c]]] - 1 < R[c].len\) (such a case \(R[c].pos\) is added to the suffixient set, \(\overline{\mathtt{LCP}}[\overline{\mathtt{LF}}[\overline{\mathtt{BWT}}[c]]] - 1\) is stored in \(R[c].len\), and \(R[c].active\) is set to false). Additionally, if \(R[\overline{\mathtt{BWT}}[i']].len < \overline{\mathtt{LCP}}[i]\), then \(n - \overline{\mathtt{SA}}[i'] + 1\) is stored in \(R[\overline{\mathtt{BWT}}[i']].pos\), \(\overline{\mathtt{LCP}}[i]\) is stored in \(R[\overline{\mathtt{BWT}}[i']].len\) and \(R[\overline{\mathtt{BWT}}[i']].active\) is set to true (with \(i' \in \{i - 1, i\}\)). Finally, after traversing the whole \(\overline{\mathtt{BWT}}\), any active candidate stored in \(R\) is added to the suffixient set. Thus, we can group the iterations into traversing within a run to keep the minimum \(\overline{\mathtt{LCP}}\) value and update \(\overline{\mathtt{LF}}\), and performing \(O(1)\) operations for each run-break.
We modify the algorithm to avoid scanning the \(\overline{\mathtt{BWT}}\) position by position and just iterate from one run-break to the next one. To achieve this, we can note that, for two consecutive run-breaks \(b_{i - 1}\) and \(b_i\), the minimum within \(\overline{\mathtt{LCP}}[b_{i - 1} \mathinner{.\,.}b_{i}]\) is exactly the length of the prefix shared by from the \((b_{i - 1})\)-th suffix to the \(b_i\)-th suffix of \(T\), so instead of iterating from \(b_{i - 1}\) to \(b_i\) we compute \(\overline{\mathtt{LCE}}(\overline{\mathtt{SA}}[b_{i - 1}], \overline{\mathtt{SA}}[b_i])\). In addition, if \(1 < b_i - b_{i - 1}\) (so, \(\overline{\mathtt{BWT}}[b_i \mathinner{.\,.}b_{i - 1} - 1] = c^{b_i - b_{i - 1}}\)), we have to count \(b_i - b_{i - 1} - 1\) additional occurrences of \(c\) to get \(\overline{\mathtt{LF}}[c]\) to point to \(b_i - 1\) as desired (we counted one when we processed \(b_{i - 1}\)), so we update \(\overline{\mathtt{LF}}[\overline{\mathtt{BWT}}[a]] = \overline{\mathtt{LF}}[\overline{\mathtt{BWT}}[a]] + (b_i - b_{i - 1} - 1)\). The rest of the algorithm just needs to know the positions of the run-breaks. 5 shows how to run the algorithm with these changes using the data structures of Kempa and Kociumaka [16].
![Figure 5: Adaptation of Cenzato et al.’s linear-time algorithm [7] for computing a smallest suffixient array](/article/2607.00204/_pdflatex/lzoyxumj.png "fig:")
The arrays \(R\) and \(\overline{\mathtt{LF}}\) use \(O(\sigma)\) space. The sublinear data structures \(\overline{\mathtt{BWT}},\overline{\mathtt{LCP}},\) and \(\overline{\mathtt{SA}}\) take \(O(p'(n,\sigma))\) space in total. Thus, the space consumption of the algorithm adds up to \(O(p'(n,\sigma) + \sigma) = O(p'(n,\sigma))\).
Regarding running-time, to compute \(occ(T,a_{i})\), we start by setting \(occ(T, a_i) = 0\) for each \(a_i\) and \(occ(T, \overline{\mathtt{BWT}}[1]) = 1\). For simplicity, we assume \(b_0 = 1\). Now, for each run-break \(b_i\), we set \(occ(T, \overline{\mathtt{BWT}}[b_i - 1]) = occ(T, \overline{\mathtt{BWT}}[b_i - 1]) + ((b_i - 1) - b_{i - 1})\) (so we are counting \((b_i - 1) - b_{i - 1}\) additional occurrences if \(\overline{\mathtt{BWT}}[b_{i - 1}, b_i - 1] = c^{(b_i - 1) - b_{i - 1} + 1}\), and none otherwise) and \(occ(T, \overline{\mathtt{BWT}}[b_i]) = occ(T, \overline{\mathtt{BWT}}[b_i]) + 1\). If \(b_{\overline{r}} < n\) (so, \(\overline{\mathtt{BWT}}[b_{\overline{r}}, n] = c^{n - b_{\overline{r}} + 1}\)), then we set \(occ(T, \overline{\mathtt{BWT}}[b_{\overline{r}}]) = occ(T, \overline{\mathtt{BWT}}[b_{\overline{r}}]) + (n - b_{\overline{r}})\) to count the occurrences within that last run. Since we perform \(O(1)\) operations on each run-break, this step takes \(O(\overline{r})\) time. The call to \(eval\) on Line 10 takes \(O(1)\) time, because the set given as the first argument is of size 1. The last call to \(eval\) on Line 15 takes \(O(\sigma)\) time as the set given has size \(O(\sigma)\). The total running-time and space consumption are then dominated by that of building the base structures [16] on \(\overline{T}\) and using them \(O(\overline{r})\) times.
This algorithm computes only a smallest suffixient set. We can sort this suffixient set in \(O(\sqrt{n} + \chi)\) time (using 3) by enhancing the prefixes with their co-lexicographical order, which can be retrieved when inserting elements in \(S\) using \(\overline{\mathtt{ISA}}\) queries. This does not increase (asymptotically) the space or time of the algorithm.