On Computing the Smallest Suffixient Set
<|reference_start|>On Computing the Smallest Suffixient Set: Let T in \Sigma^n be a text over alphabet \Sigma. A suffixient set S \subseteq [n] for T is a set of positions such that, for every one-character right-extension T[i,j] of every right-maximal substring T[i,j-1] of T, there exists x in S such that T[i,j] is a suffix of T[1,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 + \bar r|\Sigma|)-time algorithm running in compressed working space (\bar 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.<|reference_end|>
@article{cenzato2024on,
    title={On Computing the Smallest Suffixient Set},
    author={Davide Cenzato, Francisco Olivares and Nicola Prezza},
    journal={arXiv preprint arXiv:2407.18753},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.18753},
    primaryClass={cs.DS}
}