Key points are not available for this paper at this time.
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.
Peter Weiner (Mon,) studied this question.