Efficient tree pattern matching
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 178-183
- https://doi.org/10.1109/sfcs.1989.63475
Abstract
A classic open problem on tree pattern matching is whether the naive O(mn)-step algorithm for finding all the occurrences of a pattern tree of size m in a text tree of size n can be improved. An O(nM/sup 0.75/ polylog(m))-step algorithm for this tree pattern matching problem is designed. The problems of linear string matching with don't care symbols and linear string max-min convolution are treated.Keywords
This publication has 11 references indexed in Scilit:
- Parallel construction of a suffix tree with applicationsAlgorithmica, 1988
- Generalized String MatchingSIAM Journal on Computing, 1987
- Data Structures for On-Line Updating of Minimum Spanning Trees, with ApplicationsSIAM Journal on Computing, 1985
- Efficient and Elegant Subword-Tree ConstructionPublished by Springer Nature ,1985
- Efficient String Matching with Don’t-Care PatternsPublished by Springer Nature ,1985
- Pattern Matching in TreesJournal of the ACM, 1982
- A Space-Economical Suffix Tree Construction AlgorithmJournal of the ACM, 1976
- Efficient string matchingCommunications of the ACM, 1975
- Linear pattern matching algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1973
- Rapid identification of repeated patterns in strings, trees and arraysPublished by Association for Computing Machinery (ACM) ,1972