Longest common extensions in trees ?
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 v 1 , v2 v 2 , w1 w 1 , and w2 w 2 be nodes of T  such that w1 w 1 and w2 w 2 are descendants of v1 v 1 and v2 v 2 respectively. LCEPP(v1,w1,v2,w2) LCE PP ( v 1 , w 1 , v 2 , w 2 ) : (pathpath LCE) return the longest common prefix of the paths v1?w1 v 1 ? w 1 and v2?w2 v 2 ? w 2 . LCEPT(v1,w1,v2) LCE PT ( v 1 , w 1 , v 2 ) : (pathtree LCE) return maximal pathpath LCE of the path v1?w1 v 1 ? w 1 and any path from v2 v 2 to a descendant leaf. LCETT(v1,v2) LCE TT ( v 1 , v 2 ) : (treetree LCE) return a maximal pathpath LCE of any pair of paths from v1 v 1 and v2 v 2 to descendant leaves.
longest common prefix suffix tree of a tree pattern matching in trees