For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Linear Time Pattern Matching Algorithm between a String and a Tree
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1994/03/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
subtree, subgraph isomorphism, string matching, suffix tree, graph algorithms,
Full Text: PDF(473.1KB)>>
This paper presents a linear time algorithm for testing whether or not there is a path <v1,・・・,vm> of an undiercted tree T (|V(T)|n) that coincides with a string ss1・・・sm (i.e., label(v1)・・・label(vm)s1・・・sm). Since any path of the tree is allowed, linear time substring matching algorithms can not be directly applied and a new method is developed. In the algorithm, O(n/m) vertices are selected from V(T) such that any path pf length more than m 2 must contain at least one of the selected vertices. A search is performed using the selected vertices as 'bases' and two tables of size O(m) are constructed for each of the selected vertices. A suffix tree, which is a well-known-data structure in string matching, is used effectively in the algorithm. From each of the selected vertices, a search is performed with traversing the suffix tree associated with s. Although the size of the alphabet is assumed to be bounded by a constant in this paper, the algorithm can be applied to the case of unbounded alphabets by increasing the time complexity to O(n log m).