Journal article
String covering with optimal covers
Journal of Discrete Algorithms, Vol.51, pp.26-38
2018
Abstract
In this paper we introduce the notion of an optimal cover. Let M denote the maximum number of positions in w covered by any repeating substring of w. Then a longest (shortest) optimal cover u is a longest (shortest) repeating substring of w that covers M positions. The advantage of this notion is that it is not only applicable to all strings, but also that it does not share the deficiencies of the existing definitions of covers. We show that both the longest and the shortest optimal covers for a given string w of length n can be computed easily and efficiently in O(n log n) time and O(n) space. We further show that the data structures used to compute optimal covers also compute the α-partial covers introduced in [10].
Details
- Title
- String covering with optimal covers
- Authors/Creators
- N. Mhaskar (Author/Creator) - McMaster UniversityW.F. Smyth (Author/Creator) - McMaster University
- Publication Details
- Journal of Discrete Algorithms, Vol.51, pp.26-38
- Publisher
- Elsevier
- Identifiers
- 991005544172007891
- Copyright
- © 2018 Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
118 File views/ downloads
122 Record Views