An O(n log n) algorithm for finding all repetitions in a string. (English) Zbl 0547.68083

Main, Michael G.; Lorentz, Richard J.

J. Algorithms 5, 422-432 (1984).

Summary: Any nonempty string of the form xx is called a repetition. An O(n log n) algorithm is presented to find all repetitions in a string of length n. The algorithm is based on a linear algorithm to find all the new repetitions formed when two strings are concatenated. It is also shown that no algorithm based on comparisons of symbols can improve O(n log n).

MSC:

68T99	Artificial intelligence
68Q25	Analysis of algorithms and problem complexity

Keywords:

algorithm; repetitions in a string