Linear Pattern Matching of Repeated Substrings



In 1973, Weiner \cite{Weiner} presented a very original algorithm that performs linear time recognition of repeated instances of a substring in a string. Weiner's approach to this problem was as important as the solution to the problem itself. The relevance of his work was immediately appreciated. The result was announced in October, 1973 at what was then SWAT (now FOCS) and some selected ideas made their way to Section 9.5 of the first edition of Aho, Hopcroft and Ullman's textbook \cite{Aho}, published half a year later. Unfortunately, Weiner's paper may be difficult for modern readers. Familiar objects such as trees and other data structures are described using notation drawn from automata theory. Typographical errors and overloading of terms contribute to the difficulty. This paper attempts to explain Weiner's result in a more accessible manner.

Bibtex Entry