On finding common subtrees (Q1208722): Difference between revisions

Let \(T\) and \(R\) be two arbitrary ordered trees, \(| T|\geq| R|\), whose nodes are labelled over an alphabet \(A\). We devise a simple solution for detecting all the common subtree 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.