On finding common subtrees (Q1208722): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:31, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On finding common subtrees |
scientific article |
Statements
On finding common subtrees (English)
0 references
16 May 1993
0 references
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.
0 references
pattern matching
0 references
suffix tree
0 references
ordered trees
0 references