Conference paper
Computing periodicities in strings: A new approach
16th Australasian Workshop on Combinatorial Algorithms (AWOCA) 2005 (Ballarat, VIC, 18/09/2005–21/09/2005)
2005
Abstract
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.
Details
- Title
- Computing periodicities in strings: A new approach
- Authors/Creators
- W.F. Smyth (Author/Creator)
- Conference
- 16th Australasian Workshop on Combinatorial Algorithms (AWOCA) 2005 (Ballarat, VIC, 18/09/2005–21/09/2005)
- Identifiers
- 991005542852807891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Conference paper
Metrics
70 File views/ downloads
75 Record Views