What question did this study set out to answer?

This research aims to improve the construction of suffixient arrays for text indexing, enabling efficient pattern matching.

June 10, 2026Open Access

Constructing Suffixient Arrays Revisited

Key Points

This research aims to improve the construction of suffixient arrays for text indexing, enabling efficient pattern matching.
Presents a one-pass construction algorithm running in O(n) time under the standard RAM model.
Utilizes data from the suffix array, longest common prefix array, and the Burrows-Wheeler transform of the reversed text.
Seeks to reduce the number of scans required compared to previous algorithms.
Demonstrates a linear time construction of suffixient arrays, improving efficiency over prior methods.
Achieves construction without multiple passes through the necessary arrays.
Proposes a significant advancement in text indexing involving maximal exact matches.

Abstract

Recently, Cenzato et al. proposed a new text index, called the suffixient array, which is a subset of the suffix array and supports locating a single pattern occurrence or finding its maximal exact matches (MEMs), assuming random access to the input text T1. . n is available. They show that, given the suffix array, the longest common prefix array, and the Burrows-Wheeler transform (BWT) of the reverse of T1. . n over an alphabet 1, …, σ, a suffixient array can be constructed in linear time. However, their construction algorithms require multiple scans of these arrays. When restricted to a single pass over the arrays, they present an alternative construction algorithm running in O (n + r log σ) time, where r is the number of runs in the BWT of the reversed text. In this paper, we present a new one-pass algorithm that constructs a suffixient array in linear time under the standard RAM model.

KI fragen

Bookmark

View Full Paper