Linear pattern matching algorithms
Peter D. Weiner · Annual Symposium on Switching & Automata Theory · 1973
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.
Cited by 1,801 works. doi:10.1109/swat.1973.13
Authors
References
- A personal communication
- The Art of Computer Programming
- The Art of Computer Programming. Volume 1: Fundamental Algorithms.
- The unpublished manuscript
- STRING-MATCHING AND OTHER PRODUCTS
- Linear Time Simulation of Deterministic Two-Way Pushdown Automata.
- Rapid identification of repeated patterns in strings, trees and arrays
- The file transmission problem