2024/11/06 by Solon P. Pissis, Pissis, Solon P. · 1 citation
Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Natural Language Processing Techniques
paper · pdf · doi:10.48550/arxiv.2411.03784
openalex publication_date 2024/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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\mathinner. . i]T[j\mathinner. . n-1]. The border tree of T can be constructed in O(n) time and answers prefix-suffix queries in O(log n + \textsfOcc) time, where \textsfOcc is the number of occurrences of T in T[0\mathinner. . i]T[j\mathinner. . 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.