On Computing the Smallest Suffixient Set

Let T in ⁿ be a text over alphabet. A suffixient set S n for T is a set of positions such that, for every one-character right-extension Ti, j of every right-maximal substring Ti, j-1 of T, there exists x in S such that Ti, j is a suffix of T1, x. It was recently shown that, given a suffixient set of cardinality q and an oracle offering fast random access on T (for example, a straight-line program), there is a data structure of O (q) words (on top of the oracle) that can quickly find all Maximal Exact Matches (MEMs) of any query pattern P in T with high probability. The paper introducing suffixient sets left open the problem of computing the smallest such set; in this paper, we solve this problem by describing a simple quadratic-time algorithm, a O (n + r||) -time algorithm running in compressed working space (r is the number of runs in the Burrows-Wheeler transform of T reversed), and an optimal O (n) -time algorithm computing the smallest suffixient set. We present an implementation of our compressed-space algorithm and show experimentally that it uses a small memory footprint on repetitive text collections.