Linear Pattern Matching of Repeated Substrings
[.pdf]
Abstract
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
