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.

[img]
Preview
PDF - Authors' Version
Download (202kB)

Abstract

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
Publishers Website: http://www.combinatorialmath.ca/jcmcc/
URI: http://researchrepository.murdoch.edu.au/id/eprint/27541
Item Control Page Item Control Page

Downloads

Downloads per month over past year