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

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

Item 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