{"ID":5551917,"CreatedAt":"2026-07-02T01:54:51.863792489Z","UpdatedAt":"2026-07-04T03:24:42.397456366Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.00389","arxiv_id":"2607.00389","title":"Efficient LCE Queries and Lexicographic Minimizers on Sliding Suffix Trees","abstract":"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 \u0026 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]).","short_abstract":"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 i...","url_abs":"https://arxiv.org/abs/2607.00389","url_pdf":"https://arxiv.org/pdf/2607.00389v1","authors":"[\"Toshiharu Minematsu\",\"Shunsuke Inenaga\"]","published":"2026-07-01T03:32:46Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}