An O(n log n) algorithm for finding all repetitions in a string

Reviewer: John B. Slater

Given a string of symbols from an alphabet, there are various questions concerning whether the string contains any repetitions; that is, substrings of symbols that are repeated adjacently. The problem of finding all repetitions in an arbitrary string is shown to be solvable in O( nlog n) comparisons where n is the length of the string. The algorithm is a recursive one based on finding the number of new repetitions that occur when two strings are concatenated. The essence is to show that if these two strings have lengths u and v respectively, then this process can be achieved in O( uv) operations. To do this, a pattern matching algorithm by Knuth, Morris, and Pratt is used [1]. This is combined with the observations that all new repetitions must straddle the join and that new repetitions of equal length will occur in blocks with consecutive starting positions. Hence, an essentially linear search is only necessary for each length. The algorithms are presented clearly in a logical, easy-to-follow fashion. A comprehensive set of references is given. The notation is helpful. A proof is given that no algorithm based on comparison of symbols with an unspecified length of alphabet can do better than O( nlog n). An alternative method due to Crochemore [2] is referenced. The method of proof also shows that all repetitions of length n/ k or greater can be found in O( nlog k) stops. Some remaining problems with finite alphabets and allowing permutations are considered.