zbMATH — the first resource for mathematics

An O(n log n) algorithm for finding all repetitions in a string. (English) Zbl 0547.68083
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).

68T99 Artificial intelligence
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI