Exact Rooted Subtree Matching in Sublinear Time

The problem of exact subtree matching is the one of deciding if a pattern tree P of m vertices is a subtree of a text tree T of n vertices, m<= n, and, in the affirmative case, finding all the occurrences of P in T. We consider ordered and non-ordered rooted trees with labeled vertices (the case of unlabeled vertices is a special case of this), and show how the problem can be solved in Theta(m + log n) time once a proper data structure is built for T in a preprocessing phase which requires Theta(n) time and space. Regarding T as an immutable text on which several queries are made, P as the contents of one such query, and assuming m=o(n), we can speak of search time sublinear in the size m+n of the overall structure. The number of occurrences of P in T does not appear in the search time because all such occurrences can be directly reconstructed from a constant output information.