On finding common subtrees (Q1208722): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(93)90198-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1984570480 / rank | |||
Normal rank |
Revision as of 23:25, 19 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