Efficient LCE Queries and Lexicographic Minimizers on Sliding Suffix Trees
This work provides efficient solutions for fundamental string processing queries on sliding windows, benefiting applications in bioinformatics and text indexing.
The paper presents a data structure for maintaining a suffix tree over a sliding window that supports amortized constant-time window shifts and worst-case constant-time LCE queries for constant-size alphabets, and also gives a constant-time per shift algorithm for reporting lexicographic minimizers.
We study longest-common-extension (LCE) queries and lexicographic minimizer maintenance on the suffix tree of a sliding window. The main difficulty is that a sliding suffix tree is maintained in an implicit Ukkonen-style form: some suffixes of the current window are not represented by leaves. We show that the longest implicit (i.e. non-leaf) suffix induces a periodic representative map that folds every implicit suffix to an explicit suffix leaf in constant time. Combined with leaf pointers [Leonard et al., PSC 2026] and a dynamic LCA data structure [Cole & Hariharan, SICOMP 2005], this yields a linear-space data structure with amortized constant-time window shifts and worst-case constant-time LCE queries over a constant-size alphabet. For minimizers, the LCE structure gives a direct exact solution, but it uses more machinery than fixed-depth comparisons require. We therefore give an alternative LCE-free algorithm that reports minimizers in constant time per window shift, which is built on BP-linked suffix trees [Sumiyoshi et al, SPIRE 2024] and a standard order maintenance data structure (e.g. [Bender et al., ESA 2002]).