Optimal prefix-suffix queries with applications
Solon P. Pissis · Society for Industrial and Applied Mathematics eBooks · 2025
We revisit the classic border tree data structure [Gu, Farach, Beigel, SODA 1994] that answers the following prefix-suffix queries on a string T of length n over an integer alphabet Σ = [0,σ ): for any i,j ∈ [0,n ) return all occurrences of T in T [0 .. i]T [j .. n — 1]. The border tree of T can be constructed in O (n ) time and answers prefix-suffix queries in O (log n + Occ) time, where Occ is the number of occurrences of T in T [0. i ]T [ j .. n — 1]. Our contribution here is the following. We present a completely different and remarkably simple data structure that can be constructed in the optimal O (n/ logσ n ) time and supports queries in the optimal O (1) time. Our result is based on a new structural lemma that lets us encode the output of any query in constant time and, space. We also show a new direct application of our result in pattern matching on node-labeled graphs.