Journal article
Enhanced string covering
Theoretical Computer Science, Vol.506, pp.102-114
2013
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.
Details
- Title
- Enhanced string covering
- Authors/Creators
- T. Flouri (Author/Creator)C.S. Iliopoulos (Author/Creator)T. Kociumaka (Author/Creator)S.P. Pissis (Author/Creator)S.J. Puglisi (Author/Creator)W.F. Smyth (Author/Creator)W. Tyczyński (Author/Creator)
- Publication Details
- Theoretical Computer Science, Vol.506, pp.102-114
- Publisher
- Elsevier BV
- Identifiers
- 991005544891107891
- Copyright
- © 2013 Elsevier B.V.
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
47 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science