Conference paper
Fast optimal algorithms for computing all the repeats in a string
Prague Stringology Conference 2008 (Czech Technical University, Prague, 01/09/2008–03/09/2008)
2008
Abstract
Given a string x = x[1..n] on an alphabet of size α, and a threshold pmin ≥ 1, we first describe a new algorithm PSY1 that, based on suffix array construction, computes all the complete nonextendible repeats in x of length p ≥ pmin. PSY1 executes in Θ(n) time independent of alphabet size and is an order of magnitude faster than the two other algorithms previously proposed for this problem. Second, we describe a new fast algorithm PSY2 for computing all complete supernonextendible repeats in x that also executes in Θ(n) time independent of alphabet size, thus asymptotically faster than methods previously proposed. Both algorithms require 9n bytes of storage, including preprocessing (with a minor caveat for PSY1). We conclude with a brief discussion of applications to bioinformatics and data compression
Details
- Title
- Fast optimal algorithms for computing all the repeats in a string
- Authors/Creators
- S.J. Puglisi (Author/Creator)W.F. Smyth (Author/Creator)M. Yusufu (Author/Creator)
- Conference
- Prague Stringology Conference 2008 (Czech Technical University, Prague, 01/09/2008–03/09/2008)
- Identifiers
- 991005540308707891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Conference paper
Metrics
115 File views/ downloads
55 Record Views