Weak Repititions in Strings

Abstract

A weak repetition in a string consists of two or more adjacent substrings which are permutations of each other. We describe a straightforward $\mathrm{\Theta }(n^2)$ algorithm which computes all the weak repetitions in a given string of length $n$ defined
on an arbitrary alphabet $A$. Using results on Fibonacci and other simple strings, we prove that this algorithm is asymptotically optimal over all known encodings of the output.