Weak repetitions in strings
L. J. Cummings, W.F. Smyth · Murdoch Research Repository (Murdoch University) · 1997
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. 1 INTRODUCTION Interest in the periodic behaviour of strings dates back to Thue [T06] at the turn of the century. Thue considered what we call here strong repetitions (equal adjacent substrings) and showed how to construct an infinitely long string on an alphabet of only three letters with no strong repetitions. (Other constructions on three letters have been discovered several times since, most recently by Dekking [D79] and Pleasants [P70] --- the latter lists several references to earlier constructions.) More recently, Erdos [E61, p. 240] considered "Abelian squares" (w...