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

Computing periodicities in strings: A new approach

Smyth, W.F. (2005) Computing periodicities in strings: A new approach. In: 16th Australasian Workshop on Combinatorial Algorithms (AWOCA) 2005, 18 - 21 September 2005, Ballarat, VIC



The most efficient methods currently available for the computation of repetitions or repeats in a string x = x[1..n] all depend on the prior computation of a suffix tree/array STx/SAx. Although these data structures can be computed in asymptotic Θ(n) time, nevertheless in practice they involve significant overhead, both in time and space. Since the number of repetitions/repeats in x can be reported in a way that is at most linear in string length, it therefore seems that it should be possible to devise less roundabout means of computing repetitions/repeats that take advantage of their infrequent occurrence. This survey paper provides background for these ideas and explores the possibilities for more efficient computation of periodicities in strings.

Item Type: Conference Paper
Item Control Page Item Control Page


Downloads per month over past year