2023/12/03 by Depuydt, Lore, Gagie, Travis, Langmead, Ben +2 · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2312.01359
We define a suffixient set for a text T [1..n] to be a set S of positions between 1 and n such that, for any edge descending from a node u to a node v in the suffix tree of T, there is an element s ∈ S such that u's path label is a suffix of T [1..s - 1] and T [s] is the first character of (u, v)'s edge label. We first show there is a suffixient set of cardinality at most 2 r, where r is the number of runs in the Burrows-Wheeler Transform of the reverse of T. We then show that, given a straight-line program for T with g rules, we can build an O (r + g)-space index with which, given a pattern P [1..m], we can find the maximal exact matches (MEMs) of P with respect to T in O (m log (σ) / log n + d log n) time, where σ is the size of the alphabet and d is the number of times we would fully or partially descend edges in the suffix tree of T while finding those MEMs.