On finding common subtrees

Let T and R be two arbitrary ordered trees, |T| ⩾ |R|, whose nodes are labelled over an alphabet A. We devise a simple solution for detecting all the common subtrees in O(|T|) time and space if the size of A is finite, and O(|T| log min (|A|, |T|)) time otherwise. We solve the problem of finding in T and R all occurrences (if any) of any given tree B in either O(|T|⧸|B|) or O(|B|+|T|⧸|B|) time. This requires to set up a simple data structure in O(|T|) time that allows to find all maximal subtrees of B in O (|B|) time and to solve other related problems.

Authors

• Roberto Grossi

Keywords

No keywords are indexed for this paper.