Weak Repititions in Strings

A weak repetition in a string consists of two or more adjacent substrings which are permutations of each other. We describe a straightforward \(\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.