2014/12/03 by Philip Bille, Paweł Gawrychowski, Bille, Philip +8
Computer Science · #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization #cs.DS
paper · pdf · doi:10.48550/arxiv.1412.1254
openalex publication_date 2014/12/03 · arxiv created 2015/07/09 · arxiv updated 2015/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The longest common extension (LCE) of two indices in a string is the length of the longest identical substrings starting at these two indices. The LCE problem asks to preprocess a string into a compact data structure that supports fast LCE queries. In this paper we generalize the LCE problem to trees and suggest a few applications of LCE in trees to tries and XML databases. Given a labeled and rooted tree T of size n, the goal is to preprocess T into a compact data structure that support the following LCE queries between subpaths and subtrees in T. Let v1, v2, w1, and w2 be nodes of T such that w1 and w2 are descendants of v1 and v2 respectively. \beginitemize \item \LCEPP(v1, w1, v2, w2): (path-path \LCE) return the longest common prefix of the paths v1 \leadsto w1 and v2 \leadsto w2. \item \LCEPT(v1, w1, v2): (path-tree \LCE) return maximal path-path LCE of the path v1 \leadsto w1 and any path from v2 to a descendant leaf. \item \LCETT(v1, v2): (tree-tree \LCE) return a maximal path-path LCE of any pair of paths from v1 and v2 to descendant leaves. \enditemize We present the first non-trivial bounds for supporting these queries. For \LCEPP queries, we present a linear-space solution with O(log* n) query time. For \LCEPT queries, we present a linear-space solution with O((loglog n)2) query time, and complement this with a lower bound showing that any path-tree LCE structure of size O(n \polylog(n)) must necessarily use Ω(loglog n) time to answer queries. For \LCETT queries, we present a time-space trade-off, that given any parameter τ, 1 ≤ τ≤ n, leads to an O(nτ) space and O(n/τ) query-time solution. This is complemented with a reduction to the the set intersection problem implying that a fast linear space solution is not likely to exist.