Catalog Home Page

Weak repetitions in strings

Cummings, L.J. and Smyth, W.F. (1997) Weak repetitions in strings. Journal of Combinatorial Mathematics and Combinatorial Computing, 24 . pp. 33-48.

PDF - Authors' Version
Download (202kB)


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.

Item Type: Journal Article
Publisher: Charles Babbage Research Centre
Publishers Website:
Item Control Page Item Control Page


Downloads per month over past year