On finding common subtrees
type: Item
instance of: scholarly article
title: On finding common subtrees
zbMATH Open document ID: 0777.68046
DOI: 10.1016/0304-3975(93)90198-3
author: Roberto Grossi
published in: Theoretical Computer Science
publication date: 1993-05-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 166969
zbMATH Keywords: pattern matching
zbMATH Keywords: suffix tree
zbMATH Keywords: ordered trees
MaRDI profile type: Publication
full work available at URL: 0304-3975(93)90198-3
OpenAlex ID: W1984570480
cites work: Efficient string matching
cites work: Q4091421
cites work: Q3690245
cites work: Q3690247
cites work: Q3758253
cites work: Variations on the Common Subexpression Problem
cites work: Q4038694
cites work: Pattern Matching in Trees
cites work: Q4125823
cites work: Q5585020
cites work: Q2736343
cites work: On the subtree isomorphism problem for ordered trees
cites work: A Space-Economical Suffix Tree Construction Algorithm
description: scientific article; zbMATH DE number 166969