Catalog Home Page

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