Linear pattern matching algorithms

作者：Peter Weiner · 年份：1973 · DOI：10.1109/swat.1973.13 · 被引用次数：1830 · 研究领域：Algorithms and Data Compression、Network Packet Processing and Optimization、Natural Language Processing Techniques

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.