Catalog Home Page

Fast optimal algorithms for computing all the repeats in a string

Puglisi, S.J., Smyth, W.F. and Yusufu, M. (2008) Fast optimal algorithms for computing all the repeats in a string. In: Prague Stringology Conference 2008, 1 - 3 September 2008, Czech Technical University, Prague

[img]
Preview

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

Publication Type: Conference Paper
Conference Website: http://www.stringology.org/
URI: http://researchrepository.murdoch.edu.au/id/eprint/28021
Item Control Page Item Control Page

Downloads

Downloads per month over past year