Optimal prefix-suffix queries with applications

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 $\mathcal{O}(n)$ time and answers prefix-suffix queries in $\mathcal{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 $\mathcal{O}(n/ log_σ n)$ time and supports queries in the optimal $\mathcal{O}(1)$ time. Our result is based on a new structural lemma that lets us encode the output of any query in constant time andspace. We also show a new direct application of our result in pattern matching on node-labeled graphs.

• View at Publisher