A Linear Time Pattern Matching Algorithm between a String and a Tree

スポンサーリンク

概要

• 論文の詳細を見る

• This paper presents a linear time algorithm for testing whether or not there is a path <v_1,…,v_m< of an undirected tree T (|V(T)|=n) that coincides with a string s = s_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 of 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).

• 1994-03-25

著者

• Akutsu Tatsuya

  Mechanical Engineering Laboratory

関連論文

• Algorithms for Finding the Largest Subtree whose Copies Cover All the Leaves
• A Minimum Path Decomposition of the Hasse Diagram for Testing the Consistency of Functional Dependencies
• An RNC Algorithm for Finding a Largest Common Subtree of Two Trees
• A Linear Time Pattern Matching Algorithm between a String and a Tree

スポンサーリンク