Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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.

Item Type: Journal Article
Publisher: Charles Babbage Research Centre
Publisher's 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