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.
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.
|Publication Type:||Journal Article|
|Publisher:||Charles Babbage Research Centre|
|Item Control Page|
Downloads per month over past year