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

Enhanced string covering

Flouri, T., Iliopoulos, C.S., Kociumaka, T., Pissis, S.P., Puglisi, S.J., Smyth, W.F. and Tyczyński, W. (2013) Enhanced string covering. Theoretical Computer Science, 506 . pp. 102-114.

Link to Published Version: http://dx.doi.org/10.1016/j.tcs.2013.08.013
*Subscription may be required

Abstract

A factor u of a string y is a cover of y if every letter of y lies within some occurrence of u in y; thus every cover u is also a border—both prefix and suffix—of y. If u is a cover of a superstring of y then u is a seed of y. Covers and seeds are two formalisations of quasiperiodicity, and there exist linear-time algorithms for computing all the covers and seeds of y. A string y covered by u thus generalises the idea of a repetition; that is, a string composed of exact concatenations of u. Even though a string is coverable somewhat more frequently than it is a repetition, still a string that can be covered by a single u is rare. As a result, seeking to find a more generally applicable and descriptive notion of cover, many articles were written on the computation of a minimum k-cover of y; that is, the minimum cardinality set of strings of length k that collectively cover y. Unfortunately, this computation turns out to be NP-hard. Therefore, in this article, we propose new, simple, easily-computed, and widely applicable notions of string covering that provide an intuitive and useful characterisation of a string: the enhanced cover; the enhanced left cover; and the enhanced left seed.

Item Type: Journal Article
Publisher: Elsevier BV
Copyright: © 2013 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/28231
Item Control Page Item Control Page