Linear pattern matching algorithms
- 1 October 1973
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 1-11
- https://doi.org/10.1109/swat.1973.13
Abstract
In 1970, Knuth, Pratt, and Morris [1] showed how to do basic pattern matching in linear time. Related problems, such as those discussed in [4], have previously been solved by efficient but sub-optimal algorithms. In this paper, we introduce an interesting data structure called a bi-tree. A linear time algorithm for obtaining a compacted version of a bi-tree associated with a given string is presented. With this construction as the basic tool, we indicate how to solve several pattern matching problems, including some from [4] in linear time.Keywords
This publication has 2 references indexed in Scilit:
- The file transmission problemPublished by Association for Computing Machinery (ACM) ,1973
- Rapid identification of repeated patterns in strings, trees and arraysPublished by Association for Computing Machinery (ACM) ,1972