A Linear Time Pattern Matching Algorithm between a String and a Tree
Tatsuya Akutsu · IEICE Transactions on Information and Systems · 1994
In this paper, we describe a linear time algorithm for testing whether or not there is a path of a tree T (¦V(T)¦= n) that coincides with a string s (¦s¦ = m). 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’. A suffix tree is used effectively in the algorithm. 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 n).