
For FullText 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
Tatsuya AKUTSU
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E77D
No.3
pp.281287 Publication Date: 1994/03/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: subtree, subgraph isomorphism, string matching, suffix tree, graph algorithms,
Full Text: PDF>>
Summary:
This paper presents a linear time algorithm for testing whether or not there is a path <v_{1},・・・,v_{m}> of an undiercted tree T (V(T)n) that coincides with a string ss_{1}・・・s_{m} (i.e., label(v_{1})・・・label(v_{m})s_{1}・・・s_{m}). 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 wellknowndata 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).

